Merge Intervals
Given an array of intervals, merge all overlapping intervals and return the array of non-overlapping intervals.
Why Interviewers Ask This
Google asks 'Merge Intervals' to evaluate a candidate's ability to handle sorting logic and edge cases in real-world scheduling or resource allocation problems. Interviewers specifically look for how you approach data normalization, your grasp of time complexity trade-offs, and whether you can systematically reduce overlapping states without missing boundary conditions.
How to Answer This Question
1. Clarify Requirements: Confirm if intervals are inclusive, if the input is sorted, and how to handle touching intervals like [1,2] and [2,3].
2. Optimize Strategy: Propose sorting the intervals by start time first. This transforms the problem into a linear scan rather than a brute-force O(n^2) comparison.
3. Initialize State: Create a result list and push the first interval as the current active range.
4. Iterate and Merge: Loop through remaining intervals. If the current interval starts before or exactly when the active one ends, extend the active end to the maximum of both ends.
5. Finalize: If no overlap exists, push the active interval to results and reset it to the new interval. Always mention O(n log n) time complexity due to sorting and O(n) space for output.
Key Points to Cover
- Explicitly stating the decision to sort by start time first
- Demonstrating clear handling of the 'touching' interval edge case
- Using a single pass linear scan after sorting for optimal performance
- Correctly identifying the max function for merging end points
- Articulating the O(n log n) time complexity clearly
Sample Answer
To solve this efficiently, I would first sort the intervals based on their starting times. This is crucial because it allows us to process overlaps sequentially without needing nested loops. For example, given [[1,3],[2,…
Common Mistakes to Avoid
- Failing to sort the input array, leading to an inefficient O(n^2) brute force solution
- Incorrectly handling edge cases where intervals just touch, such as [1,2] and [2,3]
- Forgetting to add the final active interval to the result list after the loop finishes
- Not considering empty input arrays or arrays with only one interval
Sound confident on this question in 5 minutes
Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.