Get started

Intervals Coding Problems: 11 Questions with Solutions

11 intervals coding problems — 1 easy · 9 medium · 1 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 5-day plan.

  • Problems: 11
  • By difficulty: 1 easy · 9 medium · 1 hard
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
  • Cost: Free on every plan; sign in to run and submit

Ranges on a line: merge the ones that overlap, insert a new one, count how many rooms a set of meetings needs, find the gaps. Sort by start and sweep is the recurring idea; the problems here practise the boundary cases — touching ends, containment, an interval that swallows several.

How intervals works, step by step

by start2–68–101–315–189–12merged1–68–1215–18012345678910111213141516171819
Merging overlapping intervals, with a sort and one sweep. Example: intervals = [[2, 6], [8, 10], [1, 3], [15, 18], [9, 12]]
  1. Each interval is a bar on the number line, in the order given. Two intervals overlap when one starts before the other ends, but in this order overlapping bars can sit far apart in the list.
  2. Sort by start: [1, 3], [2, 6], [8, 10], [9, 12], [15, 18]. Now anything that overlaps the interval being built comes straight after it, so one sweep from left to right finds every merge.
  3. The sweep opens the first merged interval with [1, 3]. Its end, 3, is what the next start gets compared with.
  4. [2, 6] starts at 2, not past the end 3, so it overlaps: the merged interval grows to [1, 6], its end now max(3, 6) = 6.
  5. [8, 10] starts at 8, past the end 6. Starts only grow from here, so nothing later can reach back: [1, 6] is final, and a new merged interval opens at [8, 10].
  6. [9, 12] starts at 9, not past the end 10, so it overlaps: the merged interval grows to [8, 12], its end now max(10, 12) = 12.
  7. [15, 18] starts at 15, past the end 12. Starts only grow from here, so nothing later can reach back: [8, 12] is final, and a new merged interval opens at [15, 18].
  8. The sweep ends with [1, 6], [8, 12] and [15, 18]: 5 intervals merged into 3. Sorting is O(n log n) and the sweep O(n), so O(n log n) in all.

Intervals study plan

9 of the 11 Intervals problems (1 easy, 7 medium and 1 hard) over 5 days, about 5 h 30 min in all — the pattern first, then easiest to hardest. After that, the other 2 in the full list below are practice at your own pace. Then move on to Greedy.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve these 2.

Day 2

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 3

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 4

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 5

Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

Next topic: Greedy

Intervals: the essentials

When to reach for it

Pairs [start, end] on a line — meetings, bookings, ranges of numbers, balloon spans, video clips — and a question about how they overlap: merge them, find the most that overlap at one point, remove the fewest so the rest are disjoint, or cover a range with as few as possible.

The pattern

Two sort orders answer most of these. Sort by start to merge: keep the last merged interval and either extend its end or begin a new one. Sort by end to keep the most non-overlapping intervals: take each one that starts after the last one taken has ended. For the maximum overlap, sweep events — +1 at every start, −1 at every end — and when a start and an end share a coordinate, process the end first if touching intervals do not overlap.

def merge(intervals):
    out = []
    for s, e in sorted(intervals):
        if out and s <= out[-1][1]:  # overlaps, or touches, the last one
            out[-1][1] = max(out[-1][1], e)
        else:
            out.append([s, e])
    return out

Cost

O(n log n) for the sort and O(n) for the sweep. The event sweep sorts 2n events, still O(n log n); with small integer coordinates a difference array makes it O(n + range).

Common mistakes

  • Not deciding whether touching intervals such as [1, 2] and [2, 3] overlap: the statement decides, and the comparison must be <= or < to match.
  • Setting the merged end to e instead of max(end, e), which breaks when one interval contains the next.
  • Sorting by start for the greedy selection, which needs end times.
  • Mutating intervals the caller still holds.

Start with

All intervals problems

Easy (1)

Medium (9)

Hard (1)

Companies that ask intervals problems

Next topic: Greedy