759 Employee Free Time

1 題目

We are given a list 

schedule

 of employees, which represents the working time for each employee.

Each employee has a list of non-overlapping 

Intervals

, and these intervals are in sorted order.

Return the list of finite intervals representing common, positive-length free time for all employees, also in sorted order.

(Even though we are representing 

Intervals

 in the form 

[x, y]

, the objects inside are 

Intervals

, not lists or arrays. For example, 

schedule[0][0].start = 1

, 

schedule[0][0].end = 2

, and 

schedule[0][0][0]

 is not defined).  Also, we wouldn't include intervals like [5, 5] in our answer, as they have zero length.

2 嘗試解

2.1 分析

給定一組勞工的上班時間組成的向量，每個元素是該勞工的工作時間區間組成的向量。求所有人的公共空閑時間區間向量。

簡單的區間合并，如果兩個區間有公共區域，則合并兩個區間。具體算法為，先将二維向量展開，然後用最小堆按照起始時間對區間排序得到Intervals，設目前結束時間為end，初始值為Intervals.top().end。

如果Intevals.top().start <= end，說明堆頂區間與之前的區間有重疊部分或者無縫銜接，可以合并，即删去堆頂元素，并且更新end，考慮到堆頂元素的結束時間不一定比目前結束時間早，是以更新規則為end = max(end, Intervals.top().end)。

如果Intervals.top().start > end，說明在堆頂區間開始之前，有空餘時間，該時間區間為(end,Intervals.top().start)，加入到結果中。再删去堆頂元素，并且更新end。

2.2 代碼

class Solution {
public:
    struct cmp{
        bool operator()(Interval&A,Interval&B){
            return A.start > B.start;
        }
    };
    vector<Interval> employeeFreeTime(vector<vector<Interval>> schedule) {
        vector<Interval> result;
        priority_queue<Interval,vector<Interval>,cmp> saver;
        for(auto person:schedule){
            for(auto interval:person){
                saver.push(interval);
            }
        }
        int end = saver.top().start;
        while(saver.size()){
            if(saver.top().start > end){
                result.push_back(Interval(end,saver.top().start));
            }
            end = max(end,saver.top().end);
            saver.pop();
        }
        return result;
    }
};
           

3 标準解

3.1 分析

考慮一個時間軸t，對于每一個時間區間interval，在t = interval.start時，balance++，在t = interval.end時，balance--。那麼balance = 0的時刻即為空閑時間。

3.2 代碼

class Solution {
public:
    vector<Interval> employeeFreeTime(vector<vector<Interval>>& a) {
        vector<Interval> res;
        map<int, int> timeline;
        for (int i = 0; i < a.size(); i++) {
            for (int j = 0; j < a[i].size(); j++) {
                timeline[a[i][j].start]++;
                timeline[a[i][j].end]--;
            }
        }
        int workers = 0;
        for (pair<int, int> p : timeline) {
            workers += p.second;
            if (!workers) res.push_back(Interval(p.first, 0));
            if (workers && !res.empty() && !res.back().end) res.back().end = p.first;
        }
        if (!res.empty()) res.pop_back();
        return res;
    }
};