IntervalsSweep LineHeap
Each employee has a schedule: a sorted list of non-overlapping busy intervals. Find the intervals of time when every employee is free. Only report free time that lies between the earliest busy start and the latest busy end of everyone combined, and only gaps with a positive length (touching busy intervals leave no gap).
Input
Line 1: m, the number of employees. Next m lines: k followed by k pairs of numbers (start end), the employee's busy intervals in sorted order.
Output
Print each common free interval on its own line as 'start end', sorted, or None if there is no common free time.
Constraints
1 <= m <= 50 1 <= k <= 10 per employee 0 <= start < end <= 10^6
Example 1
Input
3 2 1 3 6 7 1 2 4 2 2 5 9 12
Output
5 6 7 9
Everyone is free from 5 to 6 and from 7 to 9.