POJ 1089 - Intervals

http://poj.org/problem?id=1089

概要

n 個の整数の区間が与えられるので，それらの和を互いに交差しない区間として昇順に並べて表現したものを答える．

制約

• 3 <= n <= 5 * 10^4
• 1 <= 整数 <= 10^6

解法

ソートしてから交差している区間をマージする．

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int N;
 8   scanf("%d", &N);
 9   static pair<int,int> is[50000];
10   for (int i = 0; i < N; i++) {
11     scanf("%d %d", &is[i].first, &is[i].second);
12   }
13   sort(is, is+N);
14 
15   pair<int,int> r = is[0];
16   for (int i = 1; i < N; i++) {
17     if (r.second < is[i].first) {
18       printf("%d %d\n", r.first, r.second);
19       r = is[i];
20     } else {
21       r.second = max(r.second, is[i].second);
22     }
23   }
24   printf("%d %d\n", r.first, r.second);
25   return 0;
26 }