Merge overlapping intervals and return the resulting set of non-overlapping intervals in sorted order.
Problem
You are given a list of intervals, where each interval is represented as [start, end]. Merge every pair of intervals that overlaps, and return the final list of non-overlapping intervals sorted by starting point.
Two intervals overlap when they share at least one point. If one interval ends exactly when another begins, treat them as overlapping for the purpose of merging.
Goal
Produce the smallest set of intervals that covers the same ranges as the input.
Notes
- The input may not be sorted.
- Intervals in the answer should be non-overlapping.
- For each merged interval, use the minimum start and maximum end among the intervals in that merged group.
Input Format
- A list of intervals
intervals, where each interval is a pair[start, end]. start <= endfor every interval.
Output Format
- Return a list of merged intervals sorted by increasing start value.
- Each interval should be represented as
[start, end].
Constraints
0 <= intervals.length- Intervals may appear in any order.
- Use inclusive endpoints when deciding whether intervals overlap.
Example 1
Input
[[1,3],[2,6],[8,10],[15,18]]
Output
[[1,6],[8,10],[15,18]]
Explanation
[1,3] overlaps with [2,6], so they merge into [1,6]. The other intervals do not overlap with that merged range.
Example 2
Input
[[1,4],[4,5]]
Output
[[1,5]]
Explanation
Because touching endpoints are treated as overlapping, the two intervals merge into [1,5].
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.