Merge overlapping intervals
Company: OpenAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
##### Question
LeetCode 56. Merge Intervals – Given a collection of intervals, merge all overlapping intervals into one and return an array of the non-overlapping intervals that cover all the intervals in the input.
https://leetcode.com/problems/merge-intervals/description/
Quick Answer: This question evaluates algorithmic problem-solving skills focused on interval manipulation, sorting and merging logic, and time/space complexity analysis within the Coding & Algorithms domain, emphasizing practical application.
Given a list of intervals where each interval is represented as [start, end], merge all overlapping intervals and return a new list of non-overlapping intervals that together cover all the intervals in the input.
Two intervals overlap if the start of one interval is less than or equal to the end of the other. Intervals that just touch at an endpoint, such as [1,4] and [4,5], should also be merged.
Return the merged intervals sorted by their start values.
Constraints
- 0 <= len(intervals) <= 10000
- intervals[i].length == 2
- -10000 <= start <= end <= 10000
Examples
Input: [[1,3],[2,6],[8,10],[15,18]]
Expected Output: [[1,6],[8,10],[15,18]]
Explanation: [1,3] and [2,6] overlap, so they merge into [1,6]. The other intervals do not overlap.
Input: [[1,4],[4,5]]
Expected Output: [[1,5]]
Explanation: The intervals touch at 4, so they are considered overlapping and merge into [1,5].
Hints
- Sorting the intervals by their start value makes it easier to detect overlaps in one pass.
- Keep track of the current merged interval and extend its end when the next interval overlaps.