Interval interview questions with worked solutions
Last updated 2026-11-19
Interval problems give you ranges, such as meetings, bookings or trips, and ask about overlap: can they all fit, how many rooms are needed, what is the fewest to remove. Almost all of them become simple once you sort the intervals, either by start time or by end time, and sweep through them.
This page covers the decision and counting problems: attendance, scheduling, capacity and selection. The problems about combining ranges into larger ones live on the separate merge intervals questions page. The sort-based greedy argument behind several answers here is explained further in greedy questions. General test advice is in the DSA coding round guide.
| Problems | 10, easy to hard |
|---|---|
| Languages | Python and Java |
| Techniques | Sorting, greedy, min-heap, sweep line |
Choosing the sort key
Sort by start time when you need to detect overlap between neighbours or allocate resources as intervals begin (meeting rooms). Sort by end time when you want to pick as many non-overlapping intervals as possible: finishing earliest leaves the most room for the rest.
Decide how touching intervals behave. [1,2] and [2,3] share a point; for meetings that is usually allowed (no overlap), for inclusive integer ranges it may count as overlap. State your convention and use strict or non-strict comparison to match it.
- Two intervals overlap when a.start < b.end and b.start < a.end.
- Maximum overlap at any time equals the resources needed: sweep line or min-heap of end times.
- Fewest removals to be non-overlapping equals n minus the maximum compatible set.
- Weighted selection needs dynamic programming, not greedy.
Sweep line in one sentence
Turn each interval into two events, a +1 at its start and a -1 at its end, sort the events by time, and keep a running total. The peak of the running total is the maximum overlap. Process end events before start events at the same time if touching intervals should not overlap.
Interval interview questions with worked solutions: questions with worked answers
1 Meeting rooms: can a person attend all meetings?
easySort by start time. If any meeting starts before the previous one ends, there is an overlap and the answer is false. Comparing only neighbours is enough after sorting, because an overlap with any earlier meeting implies an overlap with the one just before it. Time O(n log n), space O(1) beyond the sort.. Edge cases: empty list or one meeting (true), meetings that touch at one time (allowed), identical meetings.
pythondef can_attend(iv): iv.sort() for i in range(1, len(iv)): if iv[i][0] < iv[i - 1][1]: return False return Truejavaimport java.util.*; class Solution { static boolean canAttend(int[][] iv) { Arrays.sort(iv, (a, b) -> Integer.compare(a[0], b[0])); for (int i = 1; i < iv.length; i++) if (iv[i][0] < iv[i - 1][1]) return false; return true; } }2 Remove covered intervals: count intervals not completely inside another.
mediumSort by start ascending and, for equal starts, by end descending, so a longer interval comes before the shorter ones it covers. Track the largest end seen so far. An interval whose end is not beyond that maximum is covered; otherwise count it and update the maximum. Time O(n log n), space O(1).. Edge cases: equal starts (the end-descending tie-break is essential), identical intervals, one interval.
pythondef remove_covered_intervals(iv): iv.sort(key=lambda x: (x[0], -x[1])) count = max_end = 0 for s, e in iv: if e > max_end: count += 1 max_end = e return countjavaimport java.util.*; class Solution { static int removeCoveredIntervals(int[][] iv) { Arrays.sort(iv, (a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(b[1], a[1])); int count = 0, maxEnd = 0; for (int[] x : iv) { if (x[1] > maxEnd) { count++; maxEnd = x[1]; } } return count; } }3 My Calendar I: book an event only if it does not overlap an existing one.
mediumStore the booked intervals. A new half-open interval [s, e) conflicts with a stored [a, b) exactly when s < b and a < e. If no stored interval conflicts, add it and return true. A balanced tree or sorted list can find the neighbours in O(log n) instead of scanning everything. Time O(n) per booking with a list, O(log n) with a sorted structure; space O(n).. Edge cases: back-to-back bookings (allowed), identical bookings, an event fully inside another.
pythonclass MyCalendar: def __init__(self): self.booked = [] def book(self, start, end): for a, b in self.booked: if start < b and a < end: return False self.booked.append((start, end)) return Truejavaimport java.util.*; class MyCalendar { private final TreeMap<Integer, Integer> m = new TreeMap<>(); boolean book(int start, int end) { Integer prev = m.floorKey(start), next = m.ceilingKey(start); if (prev != null && m.get(prev) > start) return false; if (next != null && next < end) return false; m.put(start, end); return true; } }4 Non-overlapping intervals: the minimum number to remove so the rest do not overlap.
mediumSort by end time and greedily keep the interval that ends earliest, since it blocks the least. Walk through: if the next interval starts before the kept one ends, it overlaps and must be removed (count it); otherwise keep it and update the kept end. The removal count is the answer. Time O(n log n), space O(1).. Edge cases: empty input (0), intervals that only touch (kept), all identical.
pythondef erase_overlap_intervals(iv): iv.sort(key=lambda x: x[1]) removed, end = 0, float('-inf') for s, e in iv: if s >= end: end = e else: removed += 1 return removedjavaimport java.util.*; class Solution { static int eraseOverlapIntervals(int[][] iv) { Arrays.sort(iv, (a, b) -> Integer.compare(a[1], b[1])); int removed = 0, end = Integer.MIN_VALUE; for (int[] x : iv) { if (x[0] >= end) end = x[1]; else removed++; } return removed; } }5 Minimum number of arrows to burst all balloons given as horizontal ranges.
mediumThis is the same sort-by-end greedy. Shoot at the end of the first balloon; every balloon that starts at or before that point is burst by the same arrow. When a balloon starts after the current arrow position, fire a new arrow at its end. For [[10,16],[2,8],[1,6],[7,12]] two arrows suffice. Time O(n log n), space O(1).. Edge cases: empty input (0), balloons sharing only an endpoint (burst together), huge coordinates (compare, do not subtract, to avoid overflow).
pythondef find_min_arrow_shots(pts): if not pts: return 0 pts.sort(key=lambda x: x[1]) arrows, end = 1, pts[0][1] for s, e in pts[1:]: if s > end: arrows += 1 end = e return arrowsjavaimport java.util.*; class Solution { static int findMinArrowShots(int[][] pts) { if (pts.length == 0) return 0; Arrays.sort(pts, (a, b) -> Integer.compare(a[1], b[1])); int arrows = 1, end = pts[0][1]; for (int i = 1; i < pts.length; i++) { if (pts[i][0] > end) { arrows++; end = pts[i][1]; } } return arrows; } }6 Meeting rooms II: the minimum number of rooms needed for all meetings.
mediumSort by start time and keep a min-heap of end times of the rooms in use. For each meeting, if the earliest-ending room is free by the meeting start, reuse it (pop its end time). Push this meeting's end time. The heap size at the end is the number of rooms ever needed at once. Time O(n log n), space O(n).. Edge cases: no meetings (0), meetings that touch (room reused), all meetings simultaneous.
pythonimport heapq def min_meeting_rooms(iv): iv.sort() heap = [] for s, e in iv: if heap and heap[0] <= s: heapq.heappop(heap) heapq.heappush(heap, e) return len(heap)javaimport java.util.*; class Solution { static int minMeetingRooms(int[][] iv) { Arrays.sort(iv, (a, b) -> Integer.compare(a[0], b[0])); PriorityQueue<Integer> heap = new PriorityQueue<>(); for (int[] x : iv) { if (!heap.isEmpty() && heap.peek() <= x[0]) heap.poll(); heap.add(x[1]); } return heap.size(); } }7 Car pooling: can all trips be completed without exceeding the vehicle capacity?
mediumEach trip [passengers, from, to] adds passengers at from and removes them at to. Collect these changes by location, sort the locations, and keep a running passenger count. If the count ever exceeds the capacity, return false. Merging changes at the same location means a drop-off and pick-up at one stop net out correctly. Time O(n log n), or O(n + range) with a fixed-size difference array; space O(n).. Edge cases: trips ending where another starts, capacity exactly reached, a single huge trip.
pythonfrom collections import defaultdict def car_pooling(trips, capacity): ev = defaultdict(int) for n, f, t in trips: ev[f] += n ev[t] -= n cur = 0 for loc in sorted(ev): cur += ev[loc] if cur > capacity: return False return Truejavaimport java.util.*; class Solution { static boolean carPooling(int[][] trips, int capacity) { TreeMap<Integer, Integer> ev = new TreeMap<>(); for (int[] t : trips) { ev.merge(t[1], t[0], Integer::sum); ev.merge(t[2], -t[0], Integer::sum); } int cur = 0; for (int d : ev.values()) { cur += d; if (cur > capacity) return false; } return true; } }8 Maximum number of events you can attend, one per day, each event running from a start day to an end day.
hardGreedy over days with a min-heap of end days. Each day, add every event that starts today, discard events already expired, and attend the one that ends soonest (pop it). When no event is available, jump to the next start day. Attending the earliest deadline first never hurts. Time O(n log n), space O(n).. Edge cases: events on the same day, expired events in the heap, a gap with no events.
pythonimport heapq def max_events(events): events.sort() heap, i, day, res, n = [], 0, 0, 0, len(events) while i < n or heap: if not heap: day = events[i][0] while i < n and events[i][0] <= day: heapq.heappush(heap, events[i][1]) i += 1 while heap and heap[0] < day: heapq.heappop(heap) if heap: heapq.heappop(heap) res += 1 day += 1 return resjavaimport java.util.*; class Solution { static int maxEvents(int[][] events) { Arrays.sort(events, (a, b) -> Integer.compare(a[0], b[0])); PriorityQueue<Integer> heap = new PriorityQueue<>(); int i = 0, day = 0, res = 0, n = events.length; while (i < n || !heap.isEmpty()) { if (heap.isEmpty()) day = events[i][0]; while (i < n && events[i][0] <= day) heap.add(events[i++][1]); while (!heap.isEmpty() && heap.peek() < day) heap.poll(); if (!heap.isEmpty()) { heap.poll(); res++; } day++; } return res; } }9 Find the maximum number of intervals that overlap at any single moment (sweep line).
mediumTurn every interval into two events, (start, +1) and (end, -1). Sort events by time; at equal times the -1 sorts first, so touching intervals do not count as overlapping. Keep a running total and record its peak. This is the general tool behind room, platform and capacity problems. Time O(n log n), space O(n).. Edge cases: empty input (0), touching intervals, identical intervals.
pythondef max_overlap(iv): events = [] for s, e in iv: events.append((s, 1)) events.append((e, -1)) events.sort() cur = best = 0 for _, d in events: cur += d best = max(best, cur) return bestjavaimport java.util.*; class Solution { static int maxOverlap(int[][] iv) { List<int[]> events = new ArrayList<>(); for (int[] x : iv) { events.add(new int[]{x[0], 1}); events.add(new int[]{x[1], -1}); } events.sort((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1])); int cur = 0, best = 0; for (int[] e : events) { cur += e[1]; best = Math.max(best, cur); } return best; } }10 Maximum profit in job scheduling: jobs with start, end and profit; pick non-overlapping jobs for the most profit.
hardGreedy fails with weights, so use dynamic programming. Sort jobs by end time. Let dp[i] be the best profit using the first i jobs. For job i either skip it (dp[i]) or take it and add the best profit among jobs that finish by its start time, found by binary search over the sorted end times. Take the larger. Time O(n log n), space O(n).. Edge cases: jobs that touch (end equal to start is compatible), one job, a high-profit job overlapping many small ones.
pythonfrom bisect import bisect_right def job_scheduling(start, end, profit): jobs = sorted(zip(start, end, profit), key=lambda x: x[1]) ends = [j[1] for j in jobs] dp = [0] * (len(jobs) + 1) for i, (s, e, p) in enumerate(jobs): k = bisect_right(ends, s, 0, i) dp[i + 1] = max(dp[i], dp[k] + p) return dp[-1]javaimport java.util.*; class Solution { static int jobScheduling(int[] start, int[] end, int[] profit) { int n = start.length; int[][] jobs = new int[n][]; for (int i = 0; i < n; i++) jobs[i] = new int[]{start[i], end[i], profit[i]}; Arrays.sort(jobs, (a, b) -> Integer.compare(a[1], b[1])); int[] dp = new int[n + 1]; for (int i = 0; i < n; i++) { int lo = 0, hi = i; while (lo < hi) { int mid = (lo + hi) / 2; if (jobs[mid][1] <= jobs[i][0]) lo = mid + 1; else hi = mid; } dp[i + 1] = Math.max(dp[i], dp[lo] + jobs[i][2]); } return dp[n]; } }
Frequently asked questions
Should I sort by start or by end?
Sort by start for overlap detection and room allocation. Sort by end when selecting the most non-overlapping intervals, because finishing earliest leaves the most space.
Do touching intervals overlap?
It depends on the problem. For half-open meetings [1,2) and [2,3) they do not overlap. State your convention and match it with < or <= in the comparison.
What is a sweep line?
Convert each interval into start and end events, sort them by time and keep a running count. The maximum of the count is the maximum overlap, which is the number of rooms or vehicles you need.
How is this different from merging intervals?
These problems decide, count or select. Merging builds new combined intervals. See merge intervals questions.
When does greedy stop working on interval problems?
When intervals carry weights or values. Then you need dynamic programming, as in the weighted job scheduling problem above.
Related guides
- Merge intervals pattern questions with worked solutions
- Greedy algorithm interview questions with worked solutions
- Sorting algorithm interview questions with worked solutions
- Top K elements interview questions with worked solutions
- Binary search interview questions with worked solutions
- Prefix sum interview questions with worked solutions
More in DSA Interview Questions
- Kadane algorithm interview questions with worked solutions
- KMP and string matching interview questions with solutions
- Knapsack DP Interview Questions
- Linked list interview questions with worked solutions
- Longest Common Subsequence (LCS) Interview Questions
- Longest Increasing Subsequence (LIS) Interview Questions
- LRU Cache and Design Data Structure Interview Questions
- Math and number theory interview questions with solutions
- Matrix interview questions with worked solutions
- Merge intervals pattern questions with worked solutions
- Minimum Spanning Tree Interview Questions
- Monotonic stack interview questions with worked solutions