C算法-貪心+排序+雙指針

leetcode435，無重疊區間。給定一個區間的集合，找到需要移除區間的最小數量，使剩餘區間互不重疊。 [ [1,2], [2,3], [3,4], [1,3] ]移除1,3即可。

leetcode452，用最少數量的箭引爆氣球。[[10,16], [2,8], [1,6], [7,12]]，分别代表每個氣球的左右距離，需要一個弓箭戳破。我們在x=6和x=11上就可以戳破[2,8],[1,6]和[10,16],[7,12]

對這種兩兩集合求交集區間的思路如下：

1、按照結束位置排序

2、創造index，start在前面，end在後面

3、以第一個start的結束位置來看，是否包含end的起始位置，進行交叉條件判斷。

leetcode56，合并區間。[[1,3],[2,6],[8,10],[15,18]]合并為[[1,6],[8,10],[15,18]]

對這種兩兩集合求并集區間的思路如下：

1、按照開始位置排序

2、創造index，start在前面，end在後面

3、以第一個start的結束位置來看，是否包含end的起始位置，進行交叉條件判斷。

leetcode253，會議室II。上下車遊戲，需要把上車和下車分别排序，如果上車人數就計數++，下車時間到了就計數-- start表示占用的資源，end表示可釋放的資源。

1、需要一個start函數，和他的index：si

2、需要一個end函數，和他的index：ei

3、如果start占用的資源時間到了end[ei]，就count釋放，不然就占用更多的資源

56

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */

int Comp(const void *a, const void *b)
{
    int ret = (*(int**)a)[0] - (*(int**)b)[0];
    if (ret != 0) {
        return ret;
    }
    return (*(int**)a)[1] - (*(int**)b)[1];
}

int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes){
    if (intervalsSize == 0) {
        * returnSize = 0;
        return NULL;
    }
    int s1, s2, cnt;
    s1 = 0;
    s2 = s1 + 1;
    cnt = 0;
    qsort(intervals, intervalsSize, sizeof(int*), Comp);
    int ** ret = (int**)malloc(sizeof(int*)*intervalsSize);
    
    * returnColumnSizes = (int*)malloc(sizeof(int)*intervalsSize);
    while(s1 < intervalsSize) {
        if (s2 < intervalsSize && intervals[s1][1] >= intervals[s2][0]) { //有交叉
            intervals[s1][1] = intervals[s1][1] > intervals[s2][1] ? intervals[s1][1] : intervals[s2][1];
            s2++;
        } else {     //無交叉，輸出s1
            ret[cnt] = (int*)malloc(sizeof(int)*2);
            ret[cnt][0] = intervals[s1][0];
            ret[cnt][1] = intervals[s1][1];
            (* returnColumnSizes)[cnt] = 2;
            cnt++; 
            s1 = s2;
            s2 = s2 + 1;
        }
    }

    * returnSize = cnt;
    return ret;
}
           

253

#define MAX 10000
int Comp(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}
int minMeetingRooms(int** intervals, int intervalsSize, int* intervalsColSize){
    int stime[MAX];
    int etime[MAX];
    int i, start, end, ret, curr;
    for (i = 0; i < intervalsSize; i++) {
        stime[i] = intervals[i][0];
        etime[i] = intervals[i][1];
    }
    qsort(stime, intervalsSize, sizeof(int), Comp);
    qsort(etime, intervalsSize, sizeof(int), Comp);

    start = 0;
    end = 0;
    ret = 0;
    curr = 0;
    while (start<intervalsSize && end < intervalsSize) {
        if (etime[end] > stime[start]){
            curr++;
            start++;
            ret = curr > ret ? curr : ret;
        } else {
            end ++;
            curr--;
        }
    }
    return ret;
}
           

435

int Comp(const void*a, const void *b)
{
	return (*(int**)a)[1] - (*(int**)b)[1];
}
int eraseOverlapIntervals(int** intervals, int intervalsSize, int* intervalsColSize) {
	if (intervalsSize == 0 || intervalsSize == 1) {
		return 0;
	}
	qsort(intervals, intervalsSize, sizeof(int*), Comp);//按照終點排序
	int start, end, count;
	start = 0;
	count = 0;
	end = start + 1;
	while (start < intervalsSize && end < intervalsSize) {
        if (intervals[start][1] <= intervals[end][0]) { //如果end的起點 比start的重點小，直接過
            start = end;
            end = end + 1;
        }
		else { // 如果起點 start 與end有重疊，有重疊，舍棄end
			end++;
			count++;
		}
	}
	return count;

}
           

452

int Comp(const void *a, const void *b) 
{
    return (*(int**)a)[1] - (*(int**)b)[1];
}
int findMinArrowShots(int** points, int pointsSize, int* pointsColSize){
    if (pointsSize == 0) {
        return 0;
    }
    if (pointsSize == 1) {
        return 1;
    }
    qsort(points, pointsSize, sizeof(int*), Comp);

    int start, end, count;
    start = 0;
    end = start + 1;
    count = 1;
    while (end < pointsSize) {
        if (points[start][1] < points[end][0]) { //start 已經戳不破下一個的氣球了
            count++;
            start = end;
            end = end + 1;
        } else {
            end++; //這個start還能用
        }
    }
    return count;
}