花花酱 LeetCode 759. Employee Free Time

题目大意：给你每个员工的日历，让你找出所有员工都有空的时间段。

Problem:

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:

Example 2:

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

Idea:

Merge Intervals (virtually)

Solution:

C++

Time complexity: O(nlogn)

Space complexity: O(n)

n is the total number of intervals, n <= 2500

Related Problems:

• [解题报告] LeetCode 56. Merge Intervals
• [解题报告] LeetCode 57. Insert Interval
• [解题报告] LeetCode 729. My Calendar – 花花酱
• [解题报告] LeetCode 731. My Calendar II – 花花酱
• 花花酱 LeetCode 732. My Calendar III