Merge Intervals

Medium

Intervals

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.

Two intervals overlap if the start of one is less than or equal to the end of the other (and vice versa).

This is the foundational intervals problem. The key insight is to sort by start time first, then merge consecutive overlapping intervals by extending the end time.

Real-world analogy: Think of merging calendar events. If you have meetings from 9-10, 9:30-11, and 10:30-12, they can all be merged into a single block from 9-12 since they overlap.

Example 1

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]

Output: [[1,6],[8,10],[15,18]]

Explanation: [1,3] and [2,6] overlap (3 >= 2), so merge them into [1,6]. The other intervals do not overlap.

Example 2

Input: intervals = [[1,4],[4,5]]

Output: [[1,5]]

Explanation: Intervals [1,4] and [4,5] are considered overlapping since they share the boundary at 4.

Example 3

Input: intervals = [[1,4],[0,4]]

Output: [[0,4]]

Explanation: After sorting by start time: [[0,4],[1,4]]. They overlap, merged to [0,4].

Constraints

•1 <= intervals.length <= 10^4
•intervals[i].length == 2
•0 <= start_i <= end_i <= 10^4

Show Hints (4)

Hint 1: What if you sorted the intervals by start time first?

Hint 2: After sorting, consecutive intervals either overlap or they do not. How can you check?

Hint 3: Two sorted intervals overlap if the second one starts before the first one ends.

Hint 4: When merging, the new end is the maximum of both ends.

Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor

Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?