The Question

Merge Intervals

Given an array of intervals, merge all overlapping intervals and return the resulting array of non-overlapping intervals in sorted order.

Java

Sort + Linear Scan

ArrayList

Questions & Insights

Clarifying Questions

Sorting: Are the input intervals guaranteed to be sorted by their start or end times? (Assumption: No, we must sort them ourselves).

Bounds: What is the range of the interval values and the number of intervals (

N

)? (Assumption:

N

up to

10^5

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

Edge Cases: How should we handle null inputs, empty arrays, or single-interval arrays? (Assumption: Return empty for null/empty, return the same for single).

Inclusive/Exclusive: Are the interval boundaries inclusive? E.g., do

[1, 2]

and

[2, 3]

overlap? (Assumption: Yes, they overlap at point 2).

Thinking Process

Sort by Start Time: The primary intuition is that sorting the intervals by their start times allows us to process them in a single linear pass. If interval

B

starts after interval

A

B

can only overlap with

A

B.start \le A.end

Greedy Merging: Initialize a list of merged intervals with the first interval. For every subsequent interval, compare its start time with the end time of the last added interval in the merged list.

Update Logic: If the current interval overlaps with the last merged one, extend the last merged interval's end time to the maximum of its current end and the new interval's end. If it doesn't overlap, it represents a new disjoint interval, so append it to the list.

Conversion: Since the number of merged intervals is unknown beforehand, use a dynamic list and convert it back to a primitive 2D array at the end for the final result.

Implementation Breakdown

Problem Set

Functional Requirements: Merge all overlapping intervals and return an array of the disjoint intervals.

Constraints:

Time complexity should be dominated by sorting:

O(N \log N)

Space complexity should be

O(N)

for the output list or

O(\log N)

for sorting overhead if the output is not counted.

Approach

Algorithm: Sorting + Linear Scan (Greedy).

Data Structure: ArrayList<int[]> for dynamic storage, Arrays.sort with a custom comparator.

Complexity:

Time:

O(N \log N)

due to sorting

N

intervals.

Space:

O(N)

to store the result (or

O(\log N)

for the recursion stack of the sorting algorithm).