問題:
http://poj.org/problem?id=1089思路:
根據(jù)interval的begin升序排列，然后對(duì)于interval A, B只存在三種情況:
A包含B、A與B相交、A與B分離
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_LEN 50001
5 struct Interval {
6 int begin, end;
7 }itvs[MAX_LEN], target[MAX_LEN];
8 int N, total;
9
10 int
11 compare(const void *arg1, const void *arg2)
12 {
13 struct Interval *a = (struct Interval *)arg1;
14 struct Interval *b = (struct Interval *)arg2;
15 if(a->begin == b->begin)
16 return a->end - b->end;
17 return a->begin - b->begin;
18 }
19
20 void
21 init()
22 {
23 int i;
24 for(i=0; i<N; i++)
25 scanf("%d %d", &itvs[i].begin, &itvs[i].end);
26 qsort(itvs, N, sizeof(struct Interval), compare);
27 total = 0;
28 }
29
30 void
31 solve()
32 {
33 int i;
34 struct Interval cur = itvs[0];
35 for(i=1; i<N; i++) {
36 if(itvs[i].begin > cur.end) {
37 target[total++] = cur;
38 cur = itvs[i];
39 } else {
40 if(itvs[i].end > cur.end)
41 cur.end = itvs[i].end;
42 }
43 }
44 target[total++] = cur;
45 }
46
47 void
48 output()
49 {
50 int i;
51 for(i=0; i<total; i++)
52 printf("%d %d\n", target[i].begin, target[i].end);
53 }
54
55 int
56 main(int argc, char **argv)
57 {
58 while(scanf("%d", &N) != EOF) {
59 init();
60 solve();
61 output();
62 }
63 }