The Question
Coding

Merge Overlapping Intervals

Given a collection of time intervals, consolidate all overlapping or adjacent ranges into a single continuous interval. The goal is to produce a simplified set of disjoint intervals that covers the same total span as the original input. Provide an implementation that handles unsorted input efficiently and accounts for varying interval lengths.
Java
Sort + Linear Scan
2D Array
Questions & Insights

Clarifying Questions

Input Format and Sorting: Is the input guaranteed to be sorted by start time? (Assumption: No, the input can be in any order, so we must sort it first.)
Constraint Boundaries: What is the maximum number of intervals and the range of start/end values? (Assumption: Up to 10^5 intervals, with values fitting in a 32-bit signed integer.)
Touch Case: Should intervals that "touch" (e.g., [1, 2] and [2, 3]) be merged? (Assumption: Yes, if the start of one interval is less than or equal to the end of the previous, they should be merged.)
Output Requirements: Should the result be returned as a new array or can we modify the input? (Assumption: Return a new int[][] representing the merged intervals.)

Thinking Process

Sort by Start Time: To process intervals linearly and determine overlaps, we must first sort the array based on the start coordinate. This ensures that for any interval i, we only need to compare it with the previous merged interval.
Greedy Merging: Maintain a "current" interval being built. For each subsequent interval in the sorted list, check if its start time is \le the end time of the current interval.
Update Logic: If an overlap exists, update the end of the current interval to be the maximum of its own end and the new interval's end. This handles cases where one interval completely contains another.
Result Accumulation: If no overlap is detected, the current interval is "finished" and added to the result list. The new interval then becomes the "current" interval for future comparisons.
Implementation Breakdown

Problem Set

Functional Requirements: 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.
Constraints:
1 \le intervals.length \le 10^4
intervals[i].length == 2
0 \le start_i \le end_i \le 10^4

Approach

Algorithm: Sorting followed by a Single-Pass Linear Scan.
Data Structure: int[][] for input/output, Arrays.sort with a custom Comparator.
Complexity:
Time: O(N \log N) due to sorting, where N is the number of intervals. The linear scan is O(N).
Space: O(N) to store the result in the worst case (no overlaps), or O(\log N) for the sorting overhead depending on the implementation of Arrays.sort.

Implementation