Codeforces #274, Division 1, A ( Division 2, C ) : Exams

問題文

　http://codeforces.com/contest/480/problem/A

問題概要

　ある学生は 科目の試験を受ける。 番の科目の試験は、本来ならば試験期間の 日目に実施されるが、教官との交渉により 日目に受験することも認められた。 番の科目の試験を受けたとき、教官は学生の記録簿に本来の試験日である を追記する。同日に受けられる試験の数に制限は無い。
　学生はできるだけ早く全ての試験を受け終えたいが、記録簿に記載された日付が広義単調増加になっていなければ不自然である。そこで、記録簿に記載される日付が広義単調増加となるように試験を受けることにした。このとき、最短で何日目に全ての試験を受け終わるか求めよ。

解法

　題意より、受験する順序に の値を並べた列は広義単調増加になっていなければなりません。また、可能であれば 日目に試験を受けた方が全科目を受け終わるのが早くなります。
　従ってまずは各受験日の情報をタプルにして をキーに昇順ソートし、この順に処理します。ある時点で 日目になっているとすると（初期状態では ）、 となっている科目は 日目に、そうでない科目は 日目に受験することで、記録簿の状態を valid に保つことができます。完了の早い順に処理しているので、最適解が得られます*1。

コード

using PII = pair<int,int>; using VPII = vector< pair<int,int> >;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) (c).begin(), (c).end()

#define fst first
#define snd second

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;

	VPII ab( n );
	REP( i, 0, n )
	{
		cin >> ab[i].fst >> ab[i].snd;
	}
	sort( ALL( ab ) );

	int d = 0;
	FOR( p, ab )
	{
		d = d <= p.snd ? p.snd : p.fst;
	}

	cout << d << endl;

	return 0;
}

*1:ちゃんと示してませんが、区間幅が全て 1 の区間スケジューリングみたいな