Merge Intervals - Solution & Explanation

Problem Overview: You’re given a list of intervals where each interval represents a start and end time. Some intervals overlap. The task is to merge all overlapping intervals and return a simplified list that covers the same ranges without duplication.

Approach 1: Sort and Merge Intervals (O(n log n) time, O(n) space)

The core idea is that overlapping intervals must appear next to each other once the intervals are sorted by start time. First, sort the intervals using their start value. Then iterate through the sorted list while maintaining a result list. For each interval, compare its start with the end of the last merged interval. If the start is less than or equal to the previous end, the intervals overlap, so update the end using max(previous_end, current_end). Otherwise, append the interval as a new entry in the result.

This approach works because sorting converts the problem into a linear scan where overlaps become easy to detect. You only compare with the most recent merged interval instead of checking all previous intervals. Sorting takes O(n log n) time and the merge pass takes O(n), resulting in O(n log n) total time. Extra space is O(n) for the output list. This is the standard solution used in most interview discussions involving array processing and sorting.

Approach 2: Interval Insertion Method (O(n log n) time, O(n) space)

This method treats the problem like repeatedly inserting intervals into a merged structure. Start by sorting intervals by start time. Maintain a current interval that represents the active merged range. As you iterate, check whether the next interval overlaps with the current one. If it does, extend the current interval’s end using max(end, next_end). If it does not, push the current interval to the result and start a new one.

The logic is similar to interval insertion problems where a new interval is merged into an existing schedule. Instead of storing every interval first and merging later, the algorithm keeps a running merged segment while scanning the list. Sorting dominates the runtime at O(n log n), and the scan is linear O(n). Space complexity remains O(n) for storing the merged output.

Recommended for interviews: The expected answer is the sorted merge approach. Interviewers want to see that you recognize the key insight: sorting intervals by start time turns overlap detection into a simple linear scan. Mentioning the naive idea of comparing every interval pair shows understanding, but implementing the sort + merge strategy demonstrates practical problem‑solving with arrays and sorting patterns commonly tested at companies like Google, Amazon, and Meta.