Merge Intervals
Medium · Intervals
You are given a list of intervals, each described by a start and an end value. Combine any intervals that overlap or touch at the endpoints into a single interval covering their full span, and return the resulting list of non-overlapping intervals. Two intervals overlap if one starts at or before the point where the other ends. The order of the returned intervals does not matter as long as the set of merged intervals is correct.
Examples
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Why: [1,3] and [2,6] share the point 2, so they combine into [1,6]; the rest stand alone.Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Why: These two intervals touch at 4, so they are treated as overlapping and merged into [1,5].Input: intervals = [[1,4],[0,4]]
Output: [[0,4]]
Why: Sorting by start gives [0,4] then [1,4], and since 1 falls inside [0,4] they merge into one.Constraints
1 <= intervals.length <= 10^4, intervals[i].length == 2, 0 <= start_i <= end_i <= 10^5
Practise it by voice
Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.
This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Merge Intervals. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.