The Question

Merge Overlapping Intervals

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input. Two intervals [a, b] and [c, d] overlap if there is a point x such that a <= x <= b and c <= x <= d (inclusive).

Java

Sorting

Greedy

Questions & Insights

Clarifying Questions

Is the input array sorted by start time? (Usually, it is not, so sorting becomes the first step).

How should we handle "touching" intervals? For example, if we have [1, 2] and [2, 3], should they be merged into [1, 3]? (Assumption: Yes, inclusive boundaries overlap).

What are the constraints on the number of intervals and the values within them? (Assumption: Up to

10^5

intervals, and values fit within a 32-bit signed integer).

What is the expected behavior for empty or null input? (Assumption: Return an empty array).

Thinking Process

Sorting for Proximity: To efficiently merge intervals, we must ensure that intervals that could overlap are adjacent. Sorting the intervals by their start time ensures that if interval

i

does not overlap with

i+1

, it cannot overlap with any interval

j > i+1

Greedy Linear Scan: Once sorted, we maintain a "current" interval being merged. We iterate through the rest. If the start of the next interval is less than or equal to the end of the current interval, they overlap. We update the end of our current interval to be the maximum of its current end and the next interval's end.

Result Management: If the next interval starts after the current interval ends, the current interval is "complete." We add it to our result set and start a new "current" interval from the one we just encountered.

Space Optimization: Since we don't know the final count of merged intervals beforehand, we can use a LinkedList or ArrayList to store the results and convert it back to a 2D array at the end.

Implementation Breakdown

Problem Set

Functional Requirements: Merge all overlapping intervals and return an array of non-overlapping intervals that cover all the intervals in the input.

Constraints:

Time complexity should be dominated by sorting:

O(N \log N)

Space complexity should be

O(N)

to store the output or

O(\log N)

for the sorting stack if we ignore the output array.

Approach

Algorithm: Greedy with Sorting.

Data Structure: int[][] and ArrayList<int[]>.

Complexity:

Time:

O(N \log N)

due to sorting

N

intervals.

Space:

O(N)

O(\text{sorting overhead})

depending on whether the output storage is counted.

Implementation

Wrap Up

Advanced Topics

Stability of Sorting: For this specific problem, if two intervals have the same start time, their relative order doesn't strictly matter because the Math.max logic handles the end times correctly regardless.

Readability vs. Performance: In Java, Arrays.sort with a primitive array is highly optimized. While we could use a custom Interval object for readability, working directly with int[] minimizes object allocation overhead, which is critical in high-performance or memory-constrained environments.

Streaming/Large Data: If the intervals were too large to fit in memory, we would implement an external sort on the start times and then perform a single-pass merge (similar to the merge step in Merge Sort) to produce the output.