Skip to content

Volume ITechnology

4.27.2 — Merge Intervals ​

LeetCode 56 · Medium · ★ Blind 75

The problem ​

Merge all overlapping intervals.

Restating the Problem: You are given an array of intervals where each interval has a start and end time. Some of these intervals may overlap. Your task is to combine all overlapping intervals into single, larger intervals, returning an array of mutually exclusive (non-overlapping) intervals that cover the exact same time spans as the original input.

  • Constraints to note: The array length is up to 10^4, so an O(n^2) approach might TLE, guiding us toward an O(n \log n) sorting-based approach.
  • Edge cases: The input array might be empty or have only one interval. Intervals can be fully contained within other intervals (e.g., [1, 10] and [2, 3]).
[[1,3],[2,6],[8,10],[15,18]]   →  [[1,6],[8,10],[15,18]]
[[1,4],[4,5]]                  →  [[1,5]]     (touching counts as overlapping)

The brute force, and where it wastes work ​

A naive approach would be to start with the first interval, scan the entire list to find any overlapping interval, merge them, and repeat this process from the beginning until a full pass reveals no new overlaps. In the worst case, every merge requires rescanning the remaining intervals, leading to an O(n^2) time complexity. This is highly inefficient because it lacks an ordered way to check overlaps.

The pattern ​

Sort by start. That is the first line of almost every interval problem, and here it is what makes the rest trivial.

Once sorted, walk the list carrying the interval you are currently building. For each next interval:

  • If it starts at or before the current one ends, they overlap — extend the current end to cover it.
  • Otherwise there is a gap, so the current interval is finished. Push it and start a new one.

Why sorting by start is enough. After sorting, any interval that overlaps the one you are building must start within it — anything starting later cannot reach back. So a single "does this start before my end" test catches every overlap, and you never have to look backwards.

The solution ​

python
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])           # (1) sort by start
        result = [intervals[0]]  # (2)

        for start, end in intervals[1:]:  # (3)
            last_end = result[-1][1]  # (4)

            if start <= last_end:                     # (5) overlap → extend
                result[-1][1] = max(last_end, end)  # (6)
            else:                                     # gap → new interval
                result.append([start, end])  # (7)

        return result
ts
function merge(intervals: number[][]): number[][] {
  intervals.sort((a, b) => a[0] - b[0]);  // (1)
  const result: number[][] = [intervals[0]];  // (2)

  for (let i = 1; i < intervals.length; i++) {  // (3)
    const [start, end] = intervals[i];
    const last = result[result.length - 1];  // (4)

    if (start <= last[1]) last[1] = Math.max(last[1], end);  // (5)
    else result.push([start, end]);  // (7)
  }

  return result;
}

Line by line ​

(1) Sort by start. Then any interval that overlaps the merged ones so far must overlap the last one, because everything earlier ends sooner or has already been folded into it.

(2) The first interval starts the answer.

(3) Look at each remaining interval in order.

(4) Where the last merged interval ends.

(5) This interval starts no later than that, so they overlap. Here <= counts touching intervals, like [1, 4] and [4, 5], as overlapping. That is the rule this problem uses.

(6) Stretch the last merged interval to cover this one. Take the larger end, because this interval may sit entirely inside the last one, as with [1, 10] and [2, 3].

(7) A gap, so this interval starts a new merged interval.

max(last_end, end) is not optional. A fully contained interval like [2,3] inside [1,10] would otherwise shrink the merged interval to [1,3]. This is the bug in this problem, and it only shows up on inputs where one interval swallows another.

start <= last_end uses <= because touching intervals merge here. [1,4] and [4,5] become [1,5].

result[-1][1] = ... mutates the last entry in place, which is cleaner than popping and re-pushing.

Code Walkthrough:

  • Sorting: We first sort the intervals based on their start times.
  • Initialization: We initialize a result list and place the first interval into it.
  • Iteration: We loop through the remaining intervals starting from index 1.
  • Overlap Check (start <= last_end): For each interval, we check if its start is less than or equal to the end of the last interval in our result list. Because the intervals are sorted by start time, we know its start time is \ge the last interval's start time. We only need to check if it starts before the last one ends.
  • Merge or Add: If it overlaps, we extend the end of the last interval in result to be the max of both ends. If it doesn't overlap, we have found a distinct non-overlapping interval, so we simply append it to result.
  • Return: Finally, we return the result list.

In JavaScript, sort() compares as strings by default, so the numeric comparator is mandatory. [[10,20],[9,15]] would sort wrongly without it.

Trace ​

[[1,3],[2,6],[8,10],[15,18]] — already sorted by start.

intervallast endoverlap?result
[1,3]——[[1,3]]
[2,6]32 ≤ 3 → extend to 6[[1,6]]
[8,10]68 > 6 → gap[[1,6],[8,10]]
[15,18]10gap[[1,6],[8,10],[15,18]]

Edge cases ​

  • One interval. It is the answer.
  • One interval inside another, like [1, 10] and [2, 3]. The max in line (6) keeps the end at 10.
  • Touching intervals, like [1, 4] and [4, 5]. They merge into [1, 5].

Complexity ​

  • Time Complexity: O(n \log n). Sorting the array dominates the time complexity. The subsequent linear scan takes O(n) time.
  • Space Complexity: O(n) or O(\log n) extra space depending on the sorting algorithm used by the language, plus O(n) to store the output.

Sorting is not avoidable here. Without an ordering there is no way to know which intervals might overlap without comparing every pair, which is O(n^2).

Sort by start or by end? ​

The question that decides most interval problems, so here is the rule:

you wantsort by
merge overlapping intervalsstart
the most non-overlapping intervals you can keepend
the fewest removals to remove all overlapsend
minimum rooms or maximum concurrencyeither, with a sweep or a heap

Sorting by end is the classic activity-selection greedy: finishing earliest leaves the most room for everything after it. That is 4.27.3.

Getting this backwards is the single most common interval mistake.

Where this goes next ​

  • Insert Interval — already sorted, so O(n). 4.27.1.
  • Partition Labels — this exact merging, with one interval per letter, hidden inside a string problem. 4.26.7.
  • Employee Free Time — merge everyone's busy intervals, then report the gaps.
  • Meeting Rooms II — counting overlaps rather than merging them. 4.27.5.
  • Real uses — calendar apps, IP range consolidation in routing tables, memory allocator free-list coalescing, and time-series bucketing all run this loop.

What the interviewer will push on ​

"Why sort by start?" So any overlapping interval must begin inside the one you are building, which makes a single forward test sufficient.

"Why max(last_end, end)?" A contained interval would otherwise shrink the merged range. Give [1,10] and [2,3].

"Do touching intervals merge?" Ask — it decides < versus <=.

"Can you avoid the sort?" Not in general. Without order you would compare every pair.

"What if intervals arrive one at a time?" Repeated merging is O(n) per insertion. An ordered map or an interval tree gives O(\log n).

One thing to volunteer: state the sort-by-start-versus-end rule. It is the one piece of knowledge that makes the whole chapter mechanical, and most candidates rediscover it problem by problem.

Next: 4.27.3 Non-overlapping Intervals — where sorting by end is the answer, and there is a real proof behind it.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet