Merge Intervals

Here is two solution for problem “Merge Interval”

1. Input, Output, Contraints

  1. Input:
  • intervals: list of [start, end] pairs
  • Example: intervals = [[1,3], [2,6], [8,10], [15,18]]
  1. Output: merged list of intervals, where overlapping ones are combined

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

  1. Constraints:
    • 1 <= len(intervals) <= 10^4
    • Each interval is [start, end], 0 <= start <= end <= 10^9
    • For the O(N) version, we assume endpoints are bounded, e.g. within [1, 1024]

2. Dry run real

2.1. O(NlogN)


1---3
   2------6
           8--10
               15----18

2.2. O(N)

i	mark[i]	active (prefix sum)	Action
1	+1	1	start → cur_start=1
2	+1	2	still inside
3	0	2	still inside
4	-1	1	still inside
5	0	1	still inside
6	0	1	still inside
7	-1	0	end → append [1,6]
8	+1	1	start → cur_start=8
9	0	1	still inside
10	0	1	still inside
11	-1	0	end → append [8,10]
12–14	0	0	nothing
15	+1	1	start → cur_start=15
16–18	0	1	still inside
19	-1	0	end → append [15,18]

3. Implement O(NlogN)

def merge_intervals_sort(intervals):
    if not intervals:
        return []

    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]

    for cur in intervals[1:]:
        last = merged[-1]
        if cur[0] <= last[1]:
            last[1] = max(last[1], cur[1])
        else:
            merged.append(cur)
    return merged

4. Implement O(N)

def merge_intervals_linear(intervals, MAX=1024):
    mark = [0] * (MAX + 2)

    for start, end in intervals:
        mark[start] += 1
        mark[end + 1] -= 1

    merged = []
    active = 0
    cur_start = None

    for i in range(1, MAX + 1):
        active += mark[i]
        if active > 0 and cur_start is None:
            cur_start = i
        elif active == 0 and cur_start is not None:
            merged.append([cur_start, i - 1])
            cur_start = None
    return merged
Last Updated On October 13, 2025