56. Merge Intervals

-
Given a collection of intervals, merge all overlapping intervals.
Example 1:
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:
Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
---
Clarifying questions
Are time stamps which are exactly the same considered overlapping - example 2
  
Intuition

 Two approaches
1. Event Scan algorithm
2. Merge intervals
---
Event Scan
Event class - capture point, and isStart boolean for each interval point
Sort with custom comparator
if point values are same Boolean.compare(e2.isStart, e1.isStart) -- put Start points first *

When counter becomes zero -- start to current point is merged interval
---
Merge Intervals

Sorting by start time allows to do Left to Right scan and merge overlapping with easy check

Set prev to 1st element

for i in 2... end
if (current start <= prev end)
   merge into prev
else
  add prev to ans
  prev = current

add prev to ans *

---
Time - O(N Log N) - sorting input array
Space - O(1) - not counting output size
---
Related problems