Codeforces Round#22 (Div 2 only) D. Segments

問題概要

x軸上のn本の線分が与えられる。x軸上にnailという点を好きなだけ置くことができて、これが線分と交わる（両端を含む）とき、その線分は"nailed"されたという。全ての線分をnailedにするために必要な最小のnailの数をもとめ、そのようなnailの座標を一組出力せよ。
条件を満たせばどのような座標を出力してもかまわない。

n≤1000を満たす。

解法

まだnailedでない線分のうち最も左にあるものから見ていき、右側の座標の最小値にnailを置いていく。
このような貪欲法の解法で正しい答えが出力される……らしい（なぜだろう）

ソースコード

void run()
{
  int n; cin>>n;
  vector<pi> seg;
  rep(i,n){
    int a,b; cin>>a>>b; if(a>b)swap(a,b);
    seg.pb(mp(a,b));
  }
  sort(all(seg));

  vi nail;
  int prev=-inf;
  rep(i,n){
    if(prev>=seg[i].first)continue;
    int mn=seg[i].second;
    for(int j=i+1;j<n;j++)mn=min(mn,seg[j].second);
    nail.pb(mn);
    prev=mn;
  }
  cout<<nail.size()<<endl;
  rep(i,nail.size())cout<<nail[i]<<(i==nail.size()-1?"\n":" ");
}