Leetcode435. 无重叠区间（C语言）

算法-贪心思想：

题目： 给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。区间的终点总是大于它的起点。区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。例: 输入: [ [1,2], [2,3], [3,4], [1,3] ] 输出: 1 解释: 移除 [1,3] 后，剩下的区间没有重叠。

思路： 将各区间按照起始点从小到大排序； 从头遍历各区间： (1) 如果当前区间和上一个区间有重叠，count++; (2) 如果当前区间和上一个区间无重叠，pre = current; 返回count;

代码：

int SelfCompare(const void *p, const void *q)
{
          
   
    int **m = (int **)p;
    int **n = (int **)q;
    if ((*m)[0] == (*n)[0]) {
          
   
        return (*m)[1] - (*n)[1];
    } else {
          
   
        return (*m)[0] - (*n)[0];   
    }
}	//按第一个排列，若第一个数相等，按后一个数排列

#define NO_OVERLAP 0
#define OVERLAP_SAME_START 1
#define OVERLAP_LOCATE_IN 2
#define OVERLAP_LOCATE_OVER 3

static int IsOverlap(int **intervals, int i, int pre){
          
   	//判断覆盖情况
    int ret = NO_OVERLAP;
    if (intervals[pre][0] == intervals[i][0]) 	//同区间起点
        ret = OVERLAP_SAME_START;
    else if (intervals[pre][1] > intervals[i][0] && intervals[pre][1] <= intervals[i][1])		//区间有交集
        ret = OVERLAP_LOCATE_IN;
    else if (intervals[pre][1] > intervals[i][1])	//区间完全重叠
        ret = OVERLAP_LOCATE_OVER;
    
    return ret;
}

int eraseOverlapIntervals(int** intervals, int intervalsSize, int* intervalsColSize){
          
   

    if (intervals == NULL || intervalsSize < 2 || intervalsColSize == NULL) 	return 0;
    
    qsort(intervals, intervalsSize, sizeof(int *), SelfCompare);	//快排
    
    int ret = 0;
    int pre = 0;
    int i = pre + 1;	//初始化
    
    while (i < intervalsSize) {
          
   
        int flag = IsOverlap(intervals, i, pre);
        if (flag != NO_OVERLAP) 	ret++;
        else 	pre = i;	//若有重复，则计数；无重叠则继续往后遍历
        
        if (flag == OVERLAP_LOCATE_OVER) {
          
   	//区间完全重叠时，直接去除，继续往后遍历
            intervals[pre][0] = intervals[i][0];
            intervals[pre][1] = intervals[i][1];
        }
        
        i++;
    }
    return ret;
}