Sweapline 扫描线

每个矩形分为左边和右边两个事件，记下对应高度
对所有事件按照x坐标排序
建立高度最大堆
扫描线
遇到左边事件，堆中加入高度
遇到右边事件，堆中删除高度
堆中最大值为组合图形现在的高度
x坐标事件处理完后，如果新高度不等于原来的高度，出现拐点，记录下来
时间复杂度nlog（n）
c++ multiset
插入删除都是log2n

919. Meeting Rooms II

class Solution {
public:
    /**
     * @param intervals: an array of meeting time intervals
     * @return: the minimum number of conference rooms required
     */
    int minMeetingRooms(vector<Interval> &intervals) {
        // Write your code here
        vector <int> start;
        vector <int> end;
        for (int i = 0; i < intervals.size(); i ++){
            start.push_back(intervals[i].start);
            end.push_back(intervals[i].end);
        }
        sort(start.begin(), start.end());
        sort(end.begin(), end.end());
        int startPointer = 0, endPointer = 0, res = 0, temp = 0;
        while (startPointer < start.size() && endPointer < end.size()){
            if (end[endPointer] <= start[startPointer]){
                endPointer += 1;
                temp -= 1;
                //cout << res << temp<< endl;
            }else{
                startPointer += 1;
                temp += 1;
                res = max(res, temp);
            }
        }
        return res;
    }
};

391. Number of Airplanes in the Sky

/**
 * Definition of Interval:
 * classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 * }
 */
bool Comparator(vector<int> o1, vector<int> o2){
    if (o1[0] == o2[0]){
        return o1[1] < o2[1];
    }
    return o1[0] < o2[0];
}
class Solution {
public:
    /**
     * @param airplanes: An interval array
     * @return: Count of airplanes are in the sky.
     */
    int countOfAirplanes(vector<Interval> &airplanes) {
        // write your code here
        vector<vector<int>> array (airplanes.size() * 2, vector<int>(2));
        int res = 0, temp = 0;
        for (int i = 0; i < airplanes.size(); i ++){
            array[2 * i][0] = airplanes[i].start;
            array[2 * i][1] = 1;
            array[2 * i + 1][0] = airplanes[i].end;
            array[2 * i + 1][1] = 0;
        }
        sort (array.begin(), array.end(), Comparator);
        for (int i = 0; i < array.size(); i ++){
            if (array[i][1] == 1){
                temp += 1;
                res = max(temp, res);
            }else{
                temp --;
            }
        }
        return res;
    }
};