← 返回 microsoft 的题目列表Output all overlapping intervals
类型：online_judge
Given a list of closed intervals intervals, each [start, end] with start <= end.
Output all overlapping interval segments (the intersections formed where two or more intervals overlap). You may output the union of all overlap segments, in increasing order (clarify exact expectation in the interview if needed).
Requirements:
You may sort by start and do a linear scan.
Output intervals sorted by start.
Constraints (reasonable for interview):
1 <= n <= 2e5
-1e9 <= start <= end <= 1e9
Examples:
Input: [[1,5],[2,6],[8,10],[9,12]] -> Output: [[2,5],[9,10]]
Input: [[1,2],[3,4]] -> Output: []
Example
Input
4
1 5
2 6
8 10
9 12
Output
2
2 5
9 10