例题（差分/扫描线）

1094-拼车
253-会议室2

扫描线例题

解法一：扫描（上车下车法）
按照上车下车操作，当发现开始空闲、停止空闲时，可判断输出结果；

class Solution {
public:
    vector<Interval> employeeFreeTime(vector<vector<Interval>> schedule) {
        // dict
        map<int,int> dict;
        for(auto &person: schedule){
            for(auto &interval: person){
                ++dict[interval.start];
                --dict[interval.end];
            }
        }
        int start = INT_MIN,end=0; // for rest
        int cur = 0;
        vector<Interval> res;
        for(auto &it: dict){
            if(cur==0 && it.second>0){ // work starts , rest stops
                end = it.first;
                if(start!=INT_MIN)
                    res.push_back(Interval(start,end));
            }
            else if(cur>0 && cur+it.second==0){ // work stops, rest starts
                start = it.first;
            }
            cur+=it.second;
        }
        return res;
    }
};

解法二：排序法

• 按照时间段开始时间排序；
• 顺序遍历，记录当前最晚的结束会议的时间，与当前会议相比，如果有空闲时间段加入结果集；

class Solution {
    static bool cmp(Interval* i1, Interval * i2){
         return i1->start < i2->start || (i1->start==i2->start && i1->end < i2->end);
    }
public:
    vector<Interval> employeeFreeTime(vector<vector<Interval>> schedule) {
        // all intervals
        vector<Interval*> intervals;
        for(auto &person:schedule)
            for(auto & interval: person)
                intervals.emplace_back(&interval);

        // sort
        sort(intervals.begin(),intervals.end(),cmp);

        // res
        vector<Interval> res;
        int start = INT_MIN;
        for(auto &interval:intervals){
            if(start<interval->start && start!=INT_MIN)
                res.emplace_back(start,interval->start);
            start=max(start,interval->end);
        }
        return res;
    }
};