最多的重叠区间层数

边界计数法（扫描线算法）：用有序map模拟时间线，起点处事件数+1、终点处事件数-1，想象有根垂直时间线扫过起点和终点，遍历map并将这些增量累加，就是过程中的事件数。

class MyCalendarTwo {
    map<int, int> timeline;
public:
    MyCalendarTwo() {
    }

    bool book(int start, int end) {
        timeline[start]++;
        timeline[end]--;
        int ongoing = 0;
        for (auto &e : timeline) {
            ongoing += e.second;
            if (ongoing >= 3) {
                timeline[start]--;
                timeline[end]++;
                return false;
            }
        }
        return true;
    }
};

最少会议室

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return false.

bool canAttendMeetings(vector<Interval>& intervals) {
    // 是否所有区间都不重叠？
    sort(intervals.begin(), intervals.end(), [](const Interval &a, const Interval &b) {
        return a.end < b.end;
    });
    int end = INT_MIN;
    for (auto &interval : intervals) {
        if (interval.start < end) return false;
        else end = interval.end;
    }
    return true;
}

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.

int minMeetingRooms(vector<Interval>& intervals) {
    // 边界计数法
    map<int, int> mp;
    for (auto & interval : intervals) {
        mp[interval.start]++;
        mp[interval.end]--;
    }
    // 遍历mp，累加进行中的事件数
    int rooms = 0, ans = 0;
    for (auto &e : mp) {
        rooms += e.second;
        ans = max(ans, rooms);
    }
    return ans;
}

公共空闲时间

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.

Example 1:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]
Explanation:
There are a total of three employees, and all common
free time intervals would be [-inf, 1], [3, 4], [10, inf].
We discard any intervals that contain inf as they aren't finite.

Example 2:

Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]]
Output: [[5,6],[7,9]]

(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.

Note:

  1. schedule and schedule[i] are lists with lengths in range [1, 50].
  2. 0 <= schedule[i].start < schedule[i].end <= 10^8.
vector<Interval> employeeFreeTime(vector<vector<Interval>>& schedule) {
    // 边界计数法
    map<int, int> timeline;
    for (auto &employee : schedule) {
        for (auto &interval : employee) {
            timeline[interval.start]++;
            timeline[interval.end]--;
        }
    }

    vector<Interval> ans;
    int event = 0, start = -1;
    for (auto &e : timeline) {
        event += e.second;
        if (event <= 0) { // 空闲时间
            if (start == -1) {
                start = e.first;
            }
        } else {
            if (start != -1) {
                ans.push_back({ start, e.first });                    
                start = -1;
            }
        }
    }       
    return ans;
}