面试题合并区间

题目：现有N个区间[a1,b1],...,[aN,bN]，若区间有重叠则合并，要求输出最终的区间结果。(合并后有多个区间则输出多个区间)

sample：现有区间[4, 9], [8, 10], [15, 20], [1, 16], 合并后的区间为[1, 20]。

解题思路：定义数据结构：

1 struct myDataType
2 {
3     unsigned int a;
4     unsigned int b;
5     bool flag;
6 };

接着按区间左端点将区间排序，再从前往后依次判断相邻两区间(假设分别为区间p1,p2)是否有重叠(Overlap)，若有重叠，则更新后一个区间(p2)，并将p1的flag设为false，最终根据flag将结果输出。

code:

 1 //判断p1  p2是否有交集
 2 bool isOverlap(myDataType *p1, myDataType *p2)
 3 {
 4     bool result = false;
 5     if(p1 == NULL || p2 == NULL)
 6         return result;
 7 
 8     if((*p1).b >= (*p2).a)
 9         result = true;
10 
11     return result;
12 }
13 //更新p1
14 void update(myDataType *p1, myDataType *p2)
15 {
16     if((*p1).b < (*p2).b)
17         (*p1).b = (*p2).b;
18 
19     if((*p1).a > (*p2).a)
20         (*p1).a = (*p2).a;
21 }
22 //比较函数 
23 int compare(const void *p1, const void *p2)
24 {
25     return ((myDataType*)p1)->a - ((myDataType*)p2)->a;
26 }
27 
28 
29 void newInterval(myDataType *p, int nLen)
30 {
31 
32     if(p == NULL || nLen <= 0)
33         return;
34     //区间排序 
35     qsort(p, nLen, sizeof(myDataType), compare);
36     int i;
37     for(i = 1; i < nLen; ++i)
38     {     //判断区间是否重叠 
39         if(isOverlap(p + i - 1, p + i))
40         {    //更新后一个区间 
41             update(p + i , p + i - 1);
42             (p + i - 1)->flag = false;
43         }
44     }
45     printf("\n最终区间:\n");
46     for(i = 0; i < nLen; ++i)
47     {
48         if((p+i)->flag == true)
49             printf("[%d,%d]\n", (p+i)->a, (p+i)->b);
50     }
51     printf("\n");
52 
53 }

相关问题：如果是对IP区间合并呢？详情请看http://www.cnblogs.com/ivorfeng/archive/2013/05/05/3061137.html