AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started

Topic

Intervals coding problems

Interval problems give you ranges on a line — meetings, bookings, time slots — and ask you to merge the overlapping ones, insert a new one, count how many rooms they need or find the gaps.

New to intervals? Read the Interval Problems: Merge, Insert and Sweep tutorial first.

11 problems · 1 easy · 9 medium · 1 hard · judged by hidden tests in 13 languages

11problems

1 easy

9 medium

1 hard

Sign in to tick off what you solve.

Study plan: 9 problems · about 5 h 30 min

Start the study plan

Next up: Meeting Rooms

How it works

Intervals, step by step

Merging overlapping intervals, with a sort and one sweep

intervals = [[2, 6], [8, 10], [1, 3], [15, 18], [9, 12]]

input2–68–101–315–189–12merged012345678910111213141516171819

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.

0:01 / 0:27Step 1 of 8
Transcript · 8 steps

Study plan

Learn intervals in 5 days

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.

  1. Day 1

    about 1 h 10 min

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

  2. Day 2

    about 1 h 10 min

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

  3. Day 3

    about 1 h 10 min

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

  4. Day 4

    about 1 h 10 min

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

  5. Day 5

    about 50 min

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

    Next topic: Greedy

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

Interval problems give you ranges on a line — meetings, bookings, time slots — and ask you to merge the overlapping ones, insert a new one, count how many rooms they need or 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.

New to intervals? Read the Interval Problems: Merge, Insert and Sweep tutorial first.

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

Common questions

What is an interval problem?

A problem whose input is a list of ranges [start, end] — meetings, bookings, time slots — and whose answer depends on how they overlap: merge them, insert one, count the most that overlap at once, or find the free gaps between them.

How do you solve interval problems?

Sort the intervals by start, then sweep once from left to right, keeping the interval you are building (or, to count rooms, a min-heap of end times). The sort dominates, so most run in O(n log n) time.

When do two intervals overlap?

[a, b] and [c, d] overlap when a ≤ d and c ≤ b: each starts before the other ends. Whether touching ends such as [1, 2] and [2, 3] count is the problem's choice — read it before writing the comparison.

How many meeting rooms does a schedule need?

As many as the meetings running at the busiest moment. Keep a min-heap of end times: a meeting that starts before the earliest end needs a new room, otherwise it reuses the room that just freed up.

Next topic: Greedy