Intervals (UVa Live Archive Europe - Southwestern - 2002/2003 Porto (Portugal))

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2663

問題

数値がciと振られた区間がn個与えられる。数値の集合Zで各区間との共通部分を取った時サイズがci以上となるものの最小のサイズを求めよ。
1<=n<=50000
0<=区間<=50000

解法

区間を右端が小さい順にソートする。あとは区間を順に見ていって区間の中で使われない部分の中で最も右から順に埋めていく。pkuでは使われて無い部分を探すのにsetを使うと間に合わないのでてきとうに平均O(1)で計算できる方法を使用した。