【C】校门外的树合并重叠区间法

解题思路: 通过合并重叠区间方式计算，避免巨大数组

注意事项: 

总树木为长度+1 

挖掘树数为初始点-末尾点+1

设2个区间为a1~a2,b1~b2 判断重叠方法为b1<=a2 && b2>=a1

参考代码:

#include <stdio.h>

#define MAX(x,y) (x)>(y)?(x):(y)

#define MIN(x,y) (x)>(y)?(y):(x)

int main() {

     int length, num;

     int span[200] ; //每2个连续单元为一个区间

     scanf("%d%d", &length, &num); //输入长度和区间数量

     length++;//两头都有树 所以+1

     int i,j;

     for (i = 0; i < 200; i++) { //初始化 为-1 ，-1代表无数据

         span[i] = -1;

     }

     for (i = 0; i < num; i++) { //输入区间

         scanf("%d%d", &span[i * 2], &span[i * 2 + 1]);

     }

     for (i = 0; i < num; i++) {  //合并重叠区间

            for (j = 0; j < num; j++) {

                 if (span[j * 2] <= span[i * 2 + 1] && span[j * 2+1 ] >= span[i * 2] && i!=j) {      //判断重叠且不比较自身

                     span[i * 2] = MIN(span[i * 2], span[j * 2]); //合并

                     span[i * 2 + 1] = MAX(span[i * 2 + 1], span[j * 2 + 1]);

                     span[j * 2] = -1; //合并后清除被合并的区间

                     span[j * 2 + 1] = -1;

                 }

          }

     }

     for (i = 0; i < num; i++) { //计算剩余树木

         if(span[i * 2]!= -1)

             length -= span[i * 2 + 1] - span[i * 2]+1;

     }

     printf("%d\n", length);

     return 0;

}