Skills101

AdvancedData Structures & Algorithms · Lesson 39 of 40 · Updated ·

Interval Problems — Merge, Insert, Meeting Rooms and Platforms

An interval is a range with a start and an end, written [start, end]: a class from 9 to 11, a train at the platform from 09:40 to 12:00, a booking of a seminar hall. Interview problems on intervals look different on the surface, but almost all of them are solved by one of three moves: sort by start, sort by end, or sweep through the start and end events in time order. This lesson covers each move with the classic problems.

1. When do two intervals overlap?

Take [a1, b1] and [a2, b2]. It is easier to say when they do not overlap: one ends before the other starts (b1 < a2 or b2 < a1). Flip that, and they overlap exactly when

a1 <= b2 and a2 <= b1

Whether touching ends count (is [1, 3] overlapping [3, 5]?) depends on the problem. For meetings, one ending at 3 and the next starting at 3 usually do not clash. Read the statement and decide between < and <= — this is the most common source of wrong answers.

def overlap(x, y):
    return x[0] <= y[1] and y[0] <= x[1]

print(overlap([1, 5], [4, 8]), overlap([1, 3], [5, 7]))
print(overlap([1, 10], [3, 4]), overlap([1, 3], [3, 5]))
True False
True True

2. Merge overlapping intervals

Problem: given intervals in any order, merge all that overlap.

Idea: sort by start. Then a new interval can only overlap the last merged block, never an earlier one, because everything earlier ends before that block began. So one pass is enough:

  • if the next start is ≤ the current block's end, extend the end to max(end, next end);
  • otherwise close the block and start a new one.

Five intervals 1 to 3, 2 to 6, 8 to 10, 9 to 12 and 15 to 18 drawn on a time line, and below them the merged blocks 1 to 6, 8 to 12 and 15 to 18

def merge(intervals):
    out = []
    for s, e in sorted(intervals):
        if out and s <= out[-1][1]:
            out[-1][1] = max(out[-1][1], e)    # extend the current block
        else:
            out.append([s, e])                  # start a new block
    return out

print(merge([[8, 10], [1, 3], [15, 18], [2, 6], [9, 12]]))
print(merge([[1, 4], [2, 3]]))
print(merge([[1, 2], [3, 4]]))
[[1, 6], [8, 12], [15, 18]]
[[1, 4]]
[[1, 2], [3, 4]]

[1, 4] and [2, 3] become [1, 4], not [1, 3] — that is why we take max of the ends. Time is O(n log n) for the sort plus O(n) for the pass.

3. Insert an interval into a sorted list

Problem: the list is already sorted and non-overlapping (for example, the booked slots of a hall). Add one new booking and merge where needed.

There is no need to sort again. Walk through the list in three parts: intervals that end before the new one starts, intervals that overlap it (merge them into it), and intervals that start after it ends.

def insert(slots, new):
    s, e = new
    out, i, n = [], 0, len(slots)
    while i < n and slots[i][1] < s:          # completely before
        out.append(slots[i]); i += 1
    while i < n and slots[i][0] <= e:         # overlapping: absorb
        s, e = min(s, slots[i][0]), max(e, slots[i][1]); i += 1
    out.append([s, e])
    out.extend(slots[i:])                     # completely after
    return out

print(insert([[1, 3], [6, 9]], [2, 5]))
print(insert([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]))
[[1, 5], [6, 9]]
[[1, 2], [3, 10], [12, 16]]

This is O(n).

4. Sweep line: minimum platforms and meeting rooms

Problem: trains arrive and leave at given times. What is the fewest platforms the station needs so no train waits? (The same question as "how many meeting rooms are needed?")

Idea: the answer is the largest number of trains present at the same moment. Turn each train into two events: an arrival (+1) and a departure (−1). Sort all events by time and walk through them, keeping a running count. The highest count is the answer.

Arrival and departure events of six trains sorted by time with a running count of trains at the station; the count reaches 3 at 11:00, so 3 platforms are needed

When an arrival and a departure happen at the same time, the order matters. If a train leaving at 11:00 frees its platform for one arriving at 11:00, process the departure first. If the problem says the platform is still busy at the departure minute, process the arrival first. The code below uses two sorted arrays and handles the common railway version, where a train arriving at the same minute as another's departure still needs its own platform:

import java.util.Arrays;

public class Main {
    static int platforms(int[] arr, int[] dep) {
        int[] a = arr.clone(), d = dep.clone();
        Arrays.sort(a);
        Arrays.sort(d);
        int i = 0, j = 0, cur = 0, best = 0;
        while (i < a.length) {
            if (a[i] <= d[j]) { cur++; i++; }     // arrival first on a tie
            else { cur--; j++; }
            best = Math.max(best, cur);
        }
        return best;
    }

    public static void main(String[] args) {
        int[] arr = {900, 940, 950, 1100, 1500, 1800};
        int[] dep = {910, 1200, 1120, 1130, 1900, 2000};
        System.out.println(platforms(arr, dep));
        System.out.println(platforms(new int[]{900, 1000}, new int[]{1000, 1100}));
        System.out.println(platforms(new int[]{100, 200, 300}, new int[]{150, 250, 350}));
    }
}
3
2
1

Sorting arrivals and departures separately is allowed because we only need the count at each moment, not which train is which. Time is O(n log n).

5. Most non-overlapping meetings (greedy by end time)

Problem: one seminar hall, many meeting requests. Choose the largest number of meetings that do not overlap. A twin question: "remove the fewest intervals so the rest do not overlap" — the answer is n − (largest non-overlapping set).

Greedy rule: sort by end time and always take the meeting that finishes first among those that still fit. Finishing early leaves the most room for the rest. (Sorting by start fails: one long early meeting can block many short ones. Sorting by length also fails on some inputs.)

def max_meetings(meetings):
    count, last_end = 0, float('-inf')
    for s, e in sorted(meetings, key=lambda m: m[1]):   # by end time
        if s >= last_end:              # starts after the last chosen one ends
            count += 1
            last_end = e
    return count

talks = [[1, 4], [3, 5], [0, 6], [5, 7], [3, 9], [5, 9], [6, 10], [8, 11], [8, 12], [2, 14], [12, 16]]
print(max_meetings(talks))
print(len(talks) - max_meetings(talks), "to remove")
print(max_meetings([[1, 100], [2, 3], [4, 5], [6, 7]]))
4
7 to remove
3

In the last line, sorting by start would take [1, 100] first and get only 1 meeting; sorting by end gets 3.

6. Pattern guide

QuestionMoveTime
Merge overlapping intervalssort by start, one passO(n log n)
Insert into a sorted listthree-part walkO(n)
Can one person attend all meetings?sort by start, check start < previous endO(n log n)
Fewest rooms / platformssweep events, running count (or a min-heap of end times)O(n log n)
Most non-overlapping / fewest removalssort by end, greedyO(n log n)
Common free time, intersection of two liststwo pointers on sorted listsO(n + m)

Common mistakes

  • Not sorting first. Merging and greedy choices only work on sorted input.
  • Using the wrong comparison for touching ends (< versus <=); decide from the statement.
  • In merge, setting the end to the new interval's end instead of the max of both ends.
  • Sorting by start for the "most meetings" problem — it must be by end.
  • Changing the input list in place when the caller still needs it; sort a copy if in doubt.

Quick recap

  • Overlap test: a1 <= b2 and a2 <= b1 (adjust for touching ends).
  • Merge: sort by start; extend the last block or start a new one.
  • Insert: before / overlapping / after, O(n).
  • Rooms and platforms: sweep +1 and −1 events; the peak count is the answer.
  • Most non-overlapping meetings: sort by end, take each meeting that fits.

Practice what you learned

📝 Quiz: Interval Problems5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →