759. Employee Free Time

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.

• Time : O(nlogn)
• Space : O(n)

/*
// Definition for an Interval.
class Interval {
public:
    int start;
    int end;

    Interval() {}

    Interval(int _start, int _end) {
        start = _start;
        end = _end;
    }
};
*/

class Solution {
public:
    vector<Interval> employeeFreeTime(vector<vector<Interval>> schedule) {
        vector<pair<int, int>> vec;
        for(auto& intervals : schedule) {
            for(auto& interval : intervals) {
                vec.push_back({interval.start, interval.end});
            }
        }
        sort(vec.begin(),vec.end());
        int ma = vec[0].second;
        vector<Interval> res;
        for(auto& [start, end] : vec) {
            if(start > ma) res.push_back(Interval(ma, start));
            ma = max(ma, end);
        }
        return res;
    }
};