Interval Problems: Merge, Insert, Meeting Rooms & Sweep Line

Interval questions are interview favourites because they model real problems (calendars, booking systems, resource allocation) and because a single comparison operator decides whether the solution is correct. They're also very learnable. There are about eight core problems, and once you see that each one is "sort by start" or "sort by end" plus a small amount of bookkeeping, the variations stop being scary.

This guide goes through each problem with the reasoning for the sort order, Python and Java code, and a dry run. The last section covers the clarifying questions and follow-ups that separate a hire from a no-hire on these problems.

Interval Fundamentals: Overlap, Representation and Sort Order

The overlap test

Two intervals [a, b] and [c, d] overlap when each one starts before the other ends:

It's easier to reason about the negation: two intervals don't overlap when one ends before the other starts (b < c or d < a). Flip that and you get the condition above. Meetings are naturally half-open: a meeting from 10 to 11 and one from 11 to 12 can share a room.

Why sorting is almost always step one

Unsorted, any interval could overlap any other, which means O(n²) comparisons. Once sorted by start, an interval can only overlap the ones immediately before it in the merged structure, so one pass is enough. The question is which key to sort by:

Merge Intervals (LeetCode 56)

Given a list of closed intervals, merge all overlapping ones. After sorting by start, keep the last merged interval. If the next interval starts at or before its end, extend it; otherwise start a new one.

def merge(intervals):
    intervals.sort(key=lambda iv: iv[0])
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)   # extend, don't overwrite
        else:
            merged.append([start, end])
    return merged

public int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
    List<int[]> merged = new ArrayList<>();
    for (int[] cur : intervals) {
        if (!merged.isEmpty() && cur[0] <= merged.get(merged.size() - 1)[1]) {
            int[] last = merged.get(merged.size() - 1);
            last[1] = Math.max(last[1], cur[1]);
        } else {
            merged.add(new int[]{cur[0], cur[1]});
        }
    }
    return merged.toArray(new int[0][]);
}

Dry run on [[1,3], [8,10], [2,6], [15,18], [17,20]], sorted to [[1,3], [2,6], [8,10], [15,18], [17,20]]:

The max on extension is the line people forget. With [1,10] followed by [2,3], overwriting the end with 3 would shrink the merged interval. Two other details interviewers notice: Java's comparator should use Integer.compare rather than a[0] - b[0], which overflows for large negative values; and in the Java code I copy the interval into a new array so the caller's input isn't mutated through the result. The LeetCode 56 deep dive covers the proof that one pass suffices.

Insert Interval (LeetCode 57)

The intervals are already sorted and non-overlapping; insert a new one and merge as needed. You could append and re-run Merge in O(n log n), but the expected answer is O(n) in three phases:

1. Copy every interval that ends before the new one starts.
2. Absorb every interval that starts at or before the new one ends, growing the new interval to cover it.
3. Copy the rest.

def insert(intervals, new_interval):
    res = []
    i, n = 0, len(intervals)
    start, end = new_interval
    while i < n and intervals[i][1] < start:      # phase 1: entirely left
        res.append(intervals[i])
        i += 1
    while i < n and intervals[i][0] <= end:       # phase 2: overlapping
        start = min(start, intervals[i][0])
        end = max(end, intervals[i][1])
        i += 1
    res.append([start, end])
    res.extend(intervals[i:])                      # phase 3: entirely right
    return res

public int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> res = new ArrayList<>();
    int i = 0, n = intervals.length;
    int start = newInterval[0], end = newInterval[1];
    while (i < n && intervals[i][1] < start) res.add(intervals[i++]);
    while (i < n && intervals[i][0] <= end) {
        start = Math.min(start, intervals[i][0]);
        end = Math.max(end, intervals[i][1]);
        i++;
    }
    res.add(new int[]{start, end});
    while (i < n) res.add(intervals[i++]);
    return res.toArray(new int[0][]);
}

Example: intervals [[1,2], [3,5], [6,7], [8,10], [12,16]], new [4,8]. Phase 1 copies [1,2]. Phase 2 absorbs [3,5], [6,7], [8,10] and grows the new interval to [3,10]. Phase 3 copies [12,16]. Result: [[1,2], [3,10], [12,16]]. The phase conditions use the closed-interval convention, so [8,10] touching the new end 8 is merged.

Meeting Rooms I and II: Can You Attend, and How Many Rooms?

Meeting Rooms (LeetCode 252)

Can one person attend all meetings? Sort by start and check that each meeting starts no earlier than the previous one ends.

def canAttendMeetings(intervals):
    intervals.sort(key=lambda iv: iv[0])
    return all(intervals[i][0] >= intervals[i - 1][1]
               for i in range(1, len(intervals)))

Comparing only adjacent pairs is enough. If every adjacent pair is disjoint, the meetings form a chain where each ends before the next starts, so meeting i−1 has the latest end of everything before i. If meeting i clears it, meeting i clears all earlier meetings too. And if any pair overlaps anywhere, some adjacent pair overlaps, so the check never misses a conflict.

Meeting Rooms II (LeetCode 253): the min-heap solution

Minimum number of conference rooms. Process meetings by start time. Keep a min-heap of end times, one per room currently booked. For each meeting, the room that frees up earliest is at the top of the heap. If it's free by the time this meeting starts, reuse it; otherwise open a new room.

import heapq

def minMeetingRooms(intervals):
    intervals.sort(key=lambda iv: iv[0])
    ends = []                                   # min-heap of end times
    for start, end in intervals:
        if ends and ends[0] <= start:
            heapq.heapreplace(ends, end)        # reuse the room that freed first
        else:
            heapq.heappush(ends, end)           # need a new room
    return len(ends)

public int minMeetingRooms(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
    PriorityQueue<Integer> ends = new PriorityQueue<>();
    for (int[] m : intervals) {
        if (!ends.isEmpty() && ends.peek() <= m[0]) ends.poll();
        ends.offer(m[1]);
    }
    return ends.size();
}

Dry run on [[1,10], [2,7], [3,19], [8,12], [10,20], [11,30]] (already sorted):

Four rooms. At time 11, meetings [3,19], [8,12], [10,20] and [11,30] are all running, so four is also a lower bound. That's the proof sketch: the heap only grows when every booked room is busy at the new start time, so the heap size never exceeds the true peak overlap, and it can't be smaller than it either.

Why reuse the earliest-ending room, not any free room? For counting rooms, any free room works. The heap just makes "is any room free?" an O(1) check, because if the earliest-ending room isn't free, none are. If the follow-up asks which room each meeting gets (LeetCode 2402, Meeting Rooms III), you'll need a second heap of free room IDs.

Meeting Rooms II without a heap: two sorted arrays

Starts and ends can be sorted separately because rooms are interchangeable: we only care how many meetings are active, not which ones.

def minMeetingRooms(intervals):
    starts = sorted(s for s, _ in intervals)
    ends = sorted(e for _, e in intervals)
    rooms = j = 0
    for s in starts:
        if s >= ends[j]:     # some meeting ended: reuse its room
            j += 1
        else:
            rooms += 1       # all booked rooms busy
    return rooms

Same O(n log n), slightly lower constants, and a nice bridge to the sweep line idea below. Interviewers at Google and Amazon commonly ask for both versions, or ask you to explain why splitting starts from ends is legal.

Sort-by-End Greedy: Non-overlapping Intervals and Minimum Arrows

Non-overlapping Intervals (LeetCode 435)

Remove the minimum number of intervals so the rest don't overlap. Equivalent: keep the maximum number of non-overlapping intervals. That's the classic activity selection problem, and the greedy rule is "always keep the interval that ends earliest among those compatible with what you've kept".

def eraseOverlapIntervals(intervals):
    intervals.sort(key=lambda iv: iv[1])        # by END
    kept = 0
    last_end = float('-inf')
    for start, end in intervals:
        if start >= last_end:                   # touching is fine (half-open)
            kept += 1
            last_end = end
    return len(intervals) - kept

public int eraseOverlapIntervals(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
    int kept = 0;
    long lastEnd = Long.MIN_VALUE;
    for (int[] iv : intervals) {
        if (iv[0] >= lastEnd) {
            kept++;
            lastEnd = iv[1];
        }
    }
    return intervals.length - kept;
}

Why earliest end wins (exchange argument): take any optimal solution. Its first interval ends no earlier than the interval g that ends first overall. Swap the optimal's first interval for g: g ends earlier, so it can't conflict with anything the optimal solution kept later. The count is unchanged, so there is an optimal solution containing g. Repeat on what's left. This kind of proof is covered in more depth in the greedy algorithms guide.

Why not sort by start? Consider [1,100], [2,3], [4,5]. Sorting by start keeps [1,100] first and blocks both short intervals. Sorting by end keeps [2,3] and [4,5]. A single counterexample like this is a strong answer when an interviewer asks "would sorting by start work?"

Minimum Number of Arrows to Burst Balloons (LeetCode 452)

Same greedy, closed intervals. Shoot each arrow at the end of the earliest-ending balloon not yet burst; it hits every balloon that starts at or before that point.

public int findMinArrowShots(int[][] points) {
    Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
    int arrows = 0;
    long pos = Long.MIN_VALUE;
    for (int[] p : points) {
        if (p[0] > pos) {          // strictly after: touching balloons share an arrow
            arrows++;
            pos = p[1];
        }
    }
    return arrows;
}

Two traps hide in this one. The coordinates go down to −2³¹, so (a, b) -> a[1] - b[1] overflows and sorts incorrectly; use Integer.compare. And starting pos at Integer.MIN_VALUE fails if a balloon starts exactly there, hence the long.

The Sweep Line Technique for Interval Problems

The sweep line reframes interval problems as a stream of events in time order. Every interval [s, e) becomes a +1 event at s and a −1 event at e. Walking the sorted events with a running count tells you exactly how many intervals are active at each moment.

def max_overlap(intervals):
    events = []
    for s, e in intervals:
        events.append((s, 1))
        events.append((e, -1))
    events.sort()          # at equal times, -1 sorts before +1
    active = best = 0
    for _, delta in events:
        active += delta
        best = max(best, active)
    return best

The tie-break is the whole game. Sorting tuples puts (t, −1) before (t, +1), so a meeting ending at 10 frees its slot before one starting at 10 claims it: half-open semantics. For closed intervals where touching counts as overlapping, process starts first by encoding them as (t, 0) and ends as (t, 1), and add or subtract based on the tag.

The sweep line generalises well beyond counting:

• Car Pooling (1094): events carry passenger counts instead of 1. With small coordinates, a difference array is the same sweep without sorting.
• Points covered by the most intervals: record the time at which best is updated.
• The Skyline Problem (218): sweep over x-coordinates with a max-heap of active heights; output a point whenever the max changes.
• Employee Free Time (759): gaps where the active count is zero.

Dynamic bookings: My Calendar I and III

When intervals arrive one at a time and you must answer after each, you need an ordered structure. In Java, TreeMap gives you floor and ceiling lookups in O(log n).

class MyCalendar {
    private final TreeMap<Integer, Integer> cal = new TreeMap<>();   // start -> end

    public boolean book(int start, int end) {
        Integer prev = cal.floorKey(start);     // latest booking starting at or before
        Integer next = cal.ceilingKey(start);   // earliest booking starting at or after
        if (prev != null && cal.get(prev) > start) return false;
        if (next != null && next < end) return false;
        cal.put(start, end);
        return true;
    }
}

class MyCalendarThree {
    private final TreeMap<Integer, Integer> delta = new TreeMap<>();

    public int book(int start, int end) {
        delta.merge(start, 1, Integer::sum);
        delta.merge(end, -1, Integer::sum);
        int active = 0, best = 0;
        for (int d : delta.values()) {          // sweep in key order
            active += d;
            best = Math.max(best, active);
        }
        return best;
    }
}

Calendar III is O(n) per booking, which is fine for LeetCode's limits. If the interviewer pushes for O(log n), the answer is a segment tree with lazy propagation over compressed coordinates. In Python, the standard library has no TreeMap; use the bisect module on a sorted list (O(n) inserts) or mention sortedcontainers.SortedList and ask if third-party libraries are allowed.

This is the same problem a booking system faces at scale. The interview version of BookMyShow or a hotel booking system needs exactly this overlap check, just backed by a database instead of a TreeMap; see designing BookMyShow for how it changes with concurrency.

Intersecting Two Sorted Interval Lists (LeetCode 986)

Both lists are sorted and internally disjoint. Use one pointer per list. The intersection of the current pair is [max of starts, min of ends] if that's non-empty. Then advance whichever interval ends first, because it can't intersect anything further in the other list.

def intervalIntersection(A, B):
    i = j = 0
    res = []
    while i < len(A) and j < len(B):
        lo = max(A[i][0], B[j][0])
        hi = min(A[i][1], B[j][1])
        if lo <= hi:
            res.append([lo, hi])
        if A[i][1] < B[j][1]:
            i += 1
        else:
            j += 1
    return res

public int[][] intervalIntersection(int[][] A, int[][] B) {
    List<int[]> res = new ArrayList<>();
    int i = 0, j = 0;
    while (i < A.length && j < B.length) {
        int lo = Math.max(A[i][0], B[j][0]);
        int hi = Math.min(A[i][1], B[j][1]);
        if (lo <= hi) res.add(new int[]{lo, hi});
        if (A[i][1] < B[j][1]) i++;
        else j++;
    }
    return res.toArray(new int[0][]);
}

O(m + n), no sorting needed. It's a direct application of the "one pointer per sequence" family from the two pointers guide.

Interval Problems in Interviews: Strategy and Pitfalls

Clarifying questions to ask before coding

• Are endpoints inclusive? Do [1,2] and [2,3] overlap?
• Is the input already sorted? Can I modify it in place?
• Can intervals be empty (start == end) or invalid (start > end)?
• How large are the coordinates? (Decides between an array sweep and sorting events, and whether you need long.)
• Are intervals given all at once or one at a time? (Static sort versus TreeMap.)

Asking these takes thirty seconds and signals that you've seen the failure modes. Interviewers often deliberately leave the touching-interval case ambiguous to see if you ask.

Decision table

Follow-ups to prepare for

• "Now intervals stream in. Keep them merged." LeetCode 352 (Data Stream as Disjoint Intervals): TreeMap keyed by start, merge with floor and ceiling neighbours on each insert.
• "Return which room each meeting is assigned to." Keep room IDs alongside end times in the heap.
• "What if there are 10⁸ intervals that don't fit in memory?" External sort by start, then a streaming merge, which only needs the current merged interval in memory.
• "Weighted intervals: maximise total value, not count." Greedy breaks; this becomes DP over intervals sorted by end, with binary search for the last compatible interval (weighted job scheduling, LeetCode 1235).

Practice set

In order: 252 Meeting Rooms, 56 Merge Intervals, 57 Insert Interval, 253 Meeting Rooms II, 435 Non-overlapping Intervals, 452 Minimum Arrows, 986 Interval List Intersections, 1094 Car Pooling, 729 My Calendar I, 759 Employee Free Time, 1235 Maximum Profit in Job Scheduling, 218 The Skyline Problem. If the heap parts felt unfamiliar, spend an hour on heap and priority queue problems first; Meeting Rooms II and the Skyline both depend on it.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.