Autocoder

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.

Problems10, easy to hard
LanguagesPython and Java
TechniquesSorting, 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.

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. 1

    Meeting rooms: can a person attend all meetings?

    easy

    Sort 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.

    python
    def can_attend(iv):
        iv.sort()
        for i in range(1, len(iv)):
            if iv[i][0] < iv[i - 1][1]:
                return False
        return True
    java
    import 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. 2

    Remove covered intervals: count intervals not completely inside another.

    medium

    Sort 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.

    python
    def 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 count
    java
    import 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. 3

    My Calendar I: book an event only if it does not overlap an existing one.

    medium

    Store 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.

    python
    class 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 True
    java
    import 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. 4

    Non-overlapping intervals: the minimum number to remove so the rest do not overlap.

    medium

    Sort 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.

    python
    def 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 removed
    java
    import 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. 5

    Minimum number of arrows to burst all balloons given as horizontal ranges.

    medium

    This 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).

    python
    def 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 arrows
    java
    import 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. 6

    Meeting rooms II: the minimum number of rooms needed for all meetings.

    medium

    Sort 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.

    python
    import 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)
    java
    import 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. 7

    Car pooling: can all trips be completed without exceeding the vehicle capacity?

    medium

    Each 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.

    python
    from 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 True
    java
    import 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. 8

    Maximum number of events you can attend, one per day, each event running from a start day to an end day.

    hard

    Greedy 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.

    python
    import 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 res
    java
    import 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. 9

    Find the maximum number of intervals that overlap at any single moment (sweep line).

    medium

    Turn 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.

    python
    def 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 best
    java
    import 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. 10

    Maximum profit in job scheduling: jobs with start, end and profit; pick non-overlapping jobs for the most profit.

    hard

    Greedy 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.

    python
    from 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]
    java
    import 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

More in DSA Interview Questions

See all in this section