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
intervals = [[2, 6], [8, 10], [1, 3], [15, 18], [9, 12]]- 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.
- 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.
- The sweep opens the first merged interval with [1, 3]. Its end, 3, is what the next start gets compared with.
- [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.
- [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].
- [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.
- [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].
- 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.
- Meeting Rooms Easy
- Car Pooling Medium
Day 2
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Merge Intervals Medium
- Insert Interval Medium
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.
- Interval List Intersections Medium
- Meeting Rooms II Medium
Day 5
Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.
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
einstead ofmax(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
- Meeting Rooms: sort, then compare neighbours.
- Merge Intervals: the sort-and-extend sweep.
- Meeting Rooms II: the most overlapping at any moment.
All intervals problems
Easy (1)
- Meeting Rooms Array, Sorting
Medium (9)
- Video Stitching Array, Greedy, Dynamic Programming
- Minimum Number of Arrows to Burst Balloons Array, Greedy, Sorting
- Car Pooling Array, Prefix Sum, Sorting
- Interval List Intersections Array, Two Pointers
- Minimum Number of Arrows to Burst Balloons Array, Greedy, Sorting
- Meeting Rooms II Array, Sorting, Heap
- Non-overlapping Intervals Array, Greedy, Sorting
- Insert Interval Array
- Merge Intervals Array, Sorting
Hard (1)
- Minimum Number of Taps to Open to Water a Garden Array, Greedy, Dynamic Programming
Companies that ask intervals problems
- Amazon 3 problems on intervals
- Google 3 problems on intervals
- Atlassian 2 problems on intervals
- Flipkart 2 problems on intervals
- Snapchat 2 problems on intervals
- Yelp 2 problems on intervals
- Capital One 1 problem on intervals
- Databricks 1 problem on intervals
- Dropbox 1 problem on intervals
- Freshworks 1 problem on intervals
- Hotstar 1 problem on intervals
- Intuit 1 problem on intervals
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