Katkat
Back

Merge Overlapping Closed Intervals

ByteDanceSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manipulate sorted data structures and manage interval boundaries to optimize overlapping segments in linear or log-linear time.

Merge Overlapping Intervals

Given a collection of closed intervals intervals, where each interval is represented as a list or tuple [start, end], merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

A closed interval [a, b] contains all real numbers x such that `a list[list[int]]:


### Constraints
- `1 <= intervals.length <= 10^4`
- `0 <= start_i <= end_i <= 10^6`

### Examples

**Example 1:**
Input: `[[1, 3], [2, 6], [8, 10], [15, 18]]`
Output: `[[1, 6], [8, 10], [15, 18]]`
Explanation: Since `[1, 3]` and `[2, 6]` overlap, merge them into `[1, 6]`.

**Example 2:**
Input: `[[1, 4], [4, 5]]`
Output: `[[1, 5]]`
Explanation: Intervals touching at a single point (e.g., `4`) are considered overlapping.

### Edge Cases
- Empty input list.
- Input with a single interval.
- Intervals that are completely nested within others (e.g., `[1, 10]` and `[2, 5]`).
- Disjoint intervals that are out of order.

Hints

Hint 1

Sorting the intervals based on their start times simplifies the merging process significantly.

Hint 2

Once sorted, you can iterate through the list and keep track of the 'current' interval being merged, comparing its end time with the start time of the next interval.

Hint 3

If the next interval's start is less than or equal to the current interval's end, merge them by updating the current interval's end to the maximum of the two end times.

Follow-up questions

  • How would you modify your solution if the input intervals were not a list, but a stream of data arriving one by one?
  • What is the time complexity of your solution, and can it be optimized if the intervals are already sorted by start time?
  • How would you handle the case where the input might contain open or half-open intervals defined by an additional boolean flag for each endpoint?