253. 会议室 II

[hey-monster]

给你一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，返回 所需会议室的最小数量 。

 

示例 1：

输入：intervals = [[0,30],[5,10],[15,20]]
输出：2
示例 2：

输入：intervals = [[7,10],[2,4]]
输出：1
 

提示：

1 <= intervals.length <= 104
0 <= starti < endi <= 106

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/meeting-rooms-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1：排序
将开始时间、结束时间，独立出来放在新数组中，其中开始对应+1，结束对应-1。
然后以时间从小到大排序，相同时间既有开始也有结束的情况，则结束排在前面。
（当前也可以放在2个单独数组中，双指针法依次遍历）

int comp(const void* a, const void* b){
    int* tmp1 = (int*)a;
    int* tmp2 = (int*)b;
    int ret = tmp1[0] - tmp2[0];
    if(ret == 0){
        ret = tmp1[1] - tmp2[1];
    }
    return ret;
}
int Max(int a, int b){
    return a > b ? a : b;
}
int minMeetingRooms(int** intervals, int intervalsSize, int* intervalsColSize){
    int current = 0;
    int ret = 0;
    int times[intervalsSize * 2][2];
    int timesSize = intervalsSize * 2;
    for(int i = 0; i < intervalsSize; ++i){
        times[i*2][0] = intervals[i][0];
        times[i*2][1] = 1;
        times[i*2 + 1][0] = intervals[i][1];
        times[i*2 + 1][1] = -1;
    }
    qsort(times, timesSize, sizeof(times[0]), comp); /* 如果同一时刻既有加也有减，减的排在前面 */
    for(int i = 0; i < timesSize; ++i){
        if(times[i][1] > 0){
            current++;
        }else{
            current--;
        }
        ret = Max(ret, current);
    }
    return ret;
}

思路2：快排 + 优先队列

/* 
排序+优先队列
首先数组按开始时间排序
然后将结束时间放入优先队列(小根堆), 这里队列不用放开始时间，因为只要结束时间放进去了，那么就说明这个房间已经被使用了
最后循环遍历:
    如果当前开始时间小于堆顶结束时间最小值，则需要房间+1，并将其结束时间入堆; 
    如果当前开始时间大于堆顶结束时间最小值，则需将之前的最早结束时间更新为当前会议的结束时间
最终堆中剩下的个数就是需要的会议室个数
*/
int comp(const void* a, const void* b){
    int* tmp1 = *(int**)a;
    int* tmp2 = *(int**)b;
    return tmp1[0] - tmp2[0];
}
int Max(int a, int b){
    return a > b ? a : b;
}
struct MinHeap {
    int* ArrayPtr;
    int Size;
    int Capacity;
};
struct MinHeap* Init(int MaxSize){
    struct MinHeap* H = malloc(sizeof(struct MinHeap));
    H->ArrayPtr = malloc(sizeof(int) * (MaxSize + 1));
    H->Size = 0;
    H->Capacity = MaxSize;
    H->ArrayPtr[0] = INT_MIN;
    return H;
}
void Insert(struct MinHeap* H, int time){
    int i;
    i = ++H->Size;
    for( ; H->ArrayPtr[i/2] > time; i /= 2){
        H->ArrayPtr[i] = H->ArrayPtr[i/2];
    }
    H->ArrayPtr[i] = time;
}
void Replace(struct MinHeap* H, int time){
    /* 堆顶元素替换为新值 */
    H->ArrayPtr[1] = time;
    /* 调整堆 */
    int Parent, Child;
    for(Parent = 1; Parent * 2 <= H->Size; Parent = Child){
        Child = Parent * 2;
        if(Child != H->Size && H->ArrayPtr[Child] > H->ArrayPtr[Child + 1]){
            Child++;
        }
        if(H->ArrayPtr[Parent] <= H->ArrayPtr[Child]){
            break;
        }else{
            int tmp = H->ArrayPtr[Parent];
            H->ArrayPtr[Parent] = H->ArrayPtr[Child];
            H->ArrayPtr[Child] = tmp;
        }
    }
}
int minMeetingRooms(int** intervals, int intervalsSize, int* intervalsColSize){
    struct MinHeap* H = Init(intervalsSize);
    qsort(intervals, intervalsSize, sizeof(int*), comp);
    /*for(int i = 0; i < intervalsSize; ++i){
        printf(" %d, %d \n", intervals[i][0], intervals[i][1]);
    }*/
    Insert(H, intervals[0][1]);
    for(int i = 1; i < intervalsSize; ++i){
        if(intervals[i][0] < H->ArrayPtr[1]){
            Insert(H, intervals[i][1]);
        }else{
            Replace(H, intervals[i][1]);
        }
    }
    return H->Size;
}