Codeforces 45 D. Event Dates

問題

出来事がn個ある。
それぞれの出来事はl[i]日目からr[i]日目のどれかに起こった。
同じ日に2つ以上の出来事が起こることはなかった。

l[i],r[i]が与えられたとき、
出来事の起き方として条件を満たすものを、どれか一通り出力せよ。
条件を満たす出来事の置き方は必ず一通りはあるものとする。

制約条件

n≦100
l[i],r[i]≦10^7

方針

出来事を左側の頂点、日を右側の頂点とし、
出来事が置きうる日を辺で結ぶと、問題で求められているのはこの二部グラフの最大マッチングを一つ求めることに他ならない。

全ての頂点を直接作ると10^7でMLEになるが、
setに入れて、使う頂点だけ覚えるようにすればn≦100なので間に合う。

ソースコード

int n,l[100],r[100];
map<int,int> p;
set<int> v;

bool match(int s){
  if(s<100){
    for(int i=l[s];i<=r[s];i++)if(!v.count(i+100)){
      v.insert(i+100);
      if(!p.count(i+100)||match(p[i+100]))return p[i+100]=s, p[s]=i+100, 1;
    }
    return 0;
  }
  rep(i,n)if(l[i]<=s-100&&s-100<=r[i]&&!v.count(i)){
    v.insert(i);
    if(!p.count(i)||match(p[i]))return p[i]=s, p[s]=i, 1;
  }
  return 0;
}
void run(){
  cin>>n;
  rep(i,n)cin>>l[i]>>r[i];
  p.clear();
  rep(i,n){
    v.clear();
    if(!p.count(i))match(i);
  }
  rep(i,n)cout<<p[i]-100<<(i==n-1?"\n":" ");
}