DSA Series: Interval (Blind 75, Java)

Overview

• Pattern cheat-sheet
• 1. Insert Interval (Medium · 57)
• 2. Merge Intervals (Medium · 56)
• 3. Non-overlapping Intervals (Medium · 435)
• 4. Meeting Rooms (Easy · 252, premium)
• 5. Meeting Rooms II (Medium · 253, premium)

Part of the DSA Blind 75 series. Track your progress on the Interview Prep page.

Targets: Visa, Mastercard, NPCI, Amex, PayU. Java 11+. All code compiled and tested against examples and edge cases.

Pattern cheat-sheet

Convention to state aloud: are intervals closed [a,b] or half-open [a,b)? Do [1,4] and [4,5] overlap? (Merge: yes, touching merges. Meeting rooms / non-overlapping: touching is fine.)

1. Insert Interval (Medium · 57)

Problem statement. Given a list of non-overlapping intervals sorted by start and a newInterval, insert it and merge if necessary; return the result sorted and non-overlapping. Example: [[1,3],[6,9]], new [2,5] -> [[1,5],[6,9]]. [[1,2],[3,5],[6,7],[8,10],[12,16]], new [4,8] -> [[1,2],[3,10],[12,16]]. Constraints: 0 <= n <= 10^4, 0 <= start <= end <= 10^5.

How the interviewer asks / follow-ups.

• "A merchant has a sorted list of blackout/maintenance windows; a new window is scheduled - update the list", "add a new rate-limit/validity period to a customer's sorted fee-slab ranges", "insert a new IP/BIN range into a sorted range table".
• Follow-ups: do it in O(log n) search + O(n) copy (binary search for the position); mutate in place with a LinkedList; many inserts -> use a TreeMap<start,end>, O(log n) each; what about deletion of a range (calendar free/busy, 715 Range Module)?
• Evaluates: handling the three phases without sorting again, boundary conditions (touching intervals), not off-by-one.

Approach 1: Brute force. Append the new interval, sort everything, run the standard merge. Time O(n log n), space O(n).

Approach 2: Linear three-phase scan (optimal). Key insight: because the input is already sorted and disjoint, intervals fall into three groups relative to new: (1) end < new.start -> entirely before, copy; (2) start <= new.end -> overlaps, absorb into new by taking min start / max end; (3) the rest are after, copy. Dry run [[1,2],[3,5],[6,7],[8,10],[12,16]], new [4,8]: copy [1,2] (2<4). [3,5]: 3<=8 overlaps -> new=[3,8]. [6,7]: -> [3,8]. [8,10]: 8<=8 -> [3,10]. [12,16]: 12>10 stop. Emit [3,10], then copy [12,16]. Result [[1,2],[3,10],[12,16]].

Java code

static int[][] insert(int[][] intervals, int[] newI) {
    List<int[]> res = new ArrayList<>();
    int i = 0, n = intervals.length;
    while (i < n && intervals[i][1] < newI[0])        // strictly before: touching counts as overlap
        res.add(intervals[i++]);
    int s = newI[0], e = newI[1];
    while (i < n && intervals[i][0] <= e) {           // overlaps: absorb
        s = Math.min(s, intervals[i][0]);
        e = Math.max(e, intervals[i][1]);
        i++;
    }
    res.add(new int[]{s, e});
    while (i < n) res.add(intervals[i++]);            // strictly after
    return res.toArray(new int[0][]);
}

Complexity

• Brute force: Time O(n log n), Space O(n).
• Linear scan: Time O(n) - single pass; Space O(n) for the output (O(1) extra).

Edge cases / pitfalls. Empty input -> just [new]; new interval before everything / after everything; new fully inside an existing one; new swallowing all; touching endpoints ([1,5] + [5,8] merges, < vs <= matters); using intervals[i][1] <= newI[0] in phase 1 would skip merging touching intervals; do not forget to add the merged interval after the overlap loop.

Pattern & related. Sorted-interval linear sweep. Related: Merge Intervals (56), Interval List Intersections (986), Range Module (715), My Calendar I-III (729-732), Data Stream as Disjoint Intervals (352).

2. Merge Intervals (Medium · 56)

Problem statement. Given an array of intervals [start, end], merge all overlapping intervals and return the non-overlapping intervals covering all input. Example: [[1,3],[2,6],[8,10],[15,18]] -> [[1,6],[8,10],[15,18]]. [[1,4],[4,5]] -> [[1,5]]. Constraints: 1 <= n <= 10^4, 0 <= start <= end <= 10^4.

How the interviewer asks / follow-ups.

• "Consolidate overlapping settlement windows / fraud-alert time ranges / downtime windows into total downtime", "merge overlapping fee-slab ranges", "compute total time a service was degraded (union length)".
• Follow-ups: input not fit in memory (external sort by start, or merge per shard then merge results); streaming/online inserts (TreeMap or Insert Interval repeatedly); compute total covered length; merge across many sorted lists (k-way merge with heap); only count overlapping with at least k intervals; should input be left unmodified?
• Evaluates: sort-by-start insight, comparator correctness (overflow-safe), max on end for contained intervals.

Approach 1: Brute force. Repeatedly scan all pairs, merging any overlapping pair until no more merges happen. Time O(n^2) per pass, up to O(n^3) total; space O(n).

Approach 2: Sort + single sweep (optimal). Key insight: after sorting by start, any interval that overlaps the current merged block must start at or before the block's end; so a single left-to-right pass with a running block suffices. Use max for the end because a later interval may be fully contained. Dry run [[1,3],[2,6],[8,10],[15,18]]: cur=[1,3]. [2,6]: 2<=3 -> cur=[1,6]. [8,10]: 8>6 -> emit [1,6], cur=[8,10]. [15,18]: emit [8,10], cur=[15,18]. End: emit [15,18]. Containment trace [[1,10],[2,3],[4,5]]: cur=[1,10]; [2,3] -> end=max(10,3)=10; [4,5] -> 10. Result [[1,10]] (a plain assignment cur[1]=a[i][1] would wrongly shrink it).

Java code

static int[][] merge(int[][] intervals) {
    if (intervals.length == 0) return new int[0][];
    int[][] a = intervals.clone();                         // do not reorder caller's array
    Arrays.sort(a, (x, y) -> Integer.compare(x[0], y[0])); // never x[0]-y[0]: can overflow
    List<int[]> res = new ArrayList<>();
    int[] cur = a[0].clone();                              // do not mutate caller's interval objects
    for (int i = 1; i < a.length; i++) {
        if (a[i][0] <= cur[1]) cur[1] = Math.max(cur[1], a[i][1]);  // overlap or touch
        else { res.add(cur); cur = a[i].clone(); }
    }
    res.add(cur);
    return res.toArray(new int[0][]);
}

Complexity

• Brute force: O(n^2) to O(n^3) time, O(n) space.
• Sort + sweep: Time O(n log n) dominated by the sort, the sweep is O(n); Space O(n) for output (+ sort space).

Edge cases / pitfalls. Single interval; touching endpoints [1,4],[4,5] merge (state your assumption; for half-open they would not); contained intervals (use max); unsorted input; identical intervals; comparator using subtraction overflows with large/negative values; mutating shared arrays.

Pattern & related. Sort by start + sweep. Related: Insert Interval (57), Meeting Rooms (252/253), Interval List Intersections (986), Employee Free Time (759), Remove Covered Intervals (1288), Merge Sorted Array.

3. Non-overlapping Intervals (Medium · 435)

Problem statement. Given intervals, return the minimum number of intervals to remove so the rest are non-overlapping (touching is allowed). Example: [[1,2],[2,3],[3,4],[1,3]] -> 1 (remove [1,3]). [[1,2],[1,2],[1,2]] -> 2. [[1,2],[2,3]] -> 0. Constraints: 1 <= n <= 10^5, -5*10^4 <= start < end <= 5*10^4.

How the interviewer asks / follow-ups.

• "Maximum number of non-conflicting jobs/batch windows you can run on one processor", "fewest booking requests to reject so no two overlap on a single resource (one HSM / one settlement slot)", "activity selection".
• Follow-ups: weighted version (each job has a profit - needs DP + binary search, Weighted Job Scheduling / 1235); why sort by end and not by start or by length (counter-examples)? Return which intervals to remove? k machines instead of one?
• Evaluates: recognizing the classic greedy and being able to justify it (exchange argument), counter-examples to wrong greedy choices.

Approach 1: Brute force. Try all subsets of intervals, keep the largest non-overlapping subset; answer = n - max. Time O(2^n * n), space O(n). Alternatively an O(n^2) DP like longest chain: sort by start, dp[i] = max kept ending at i.

Approach 2: DP (sort by start). dp[i] = 1 + max(dp[j]) over j < i with end_j <= start_i. Time O(n^2); with binary search O(n log n) - this is the base for the weighted variant.

Approach 3: Greedy by earliest end (optimal). Key insight: among intervals, always keep the one that finishes first; it leaves the most room for the rest. Sort by end; keep an interval if it starts at or after the last kept end; otherwise it overlaps - drop it (we already hold the one with the earlier end). Answer = n - kept. Why not sort by start? [1,100],[2,3],[4,5] - keeping [1,100] first is a disaster. Why not shortest-first? [1,10],[9,11],[10,20]... shortest [9,11] blocks the two others. Dry run [[1,2],[2,3],[3,4],[1,3]]: sorted by end: [1,2],[2,3],[1,3],[3,4] (ties on end order does not matter). Keep [1,2] (end=2). [2,3]: 2>=2 keep (end=3). [1,3]: 1<3 drop. [3,4]: 3>=3 keep. Kept 3, removed 1.

Java code

static int eraseOverlapIntervals(int[][] intervals) {
    if (intervals.length == 0) return 0;
    int[][] a = intervals.clone();
    Arrays.sort(a, (x, y) -> Integer.compare(x[1], y[1]));   // by END
    int kept = 1, end = a[0][1];
    for (int i = 1; i < a.length; i++) {
        if (a[i][0] >= end) {          // touching is OK
            kept++;
            end = a[i][1];
        }                              // else overlaps: skip (counts as removed)
    }
    return a.length - kept;
}

Complexity

• Brute force: O(2^n * n) time, O(n) space.
• DP: O(n^2) time (O(n log n) with binary search), O(n) space.
• Greedy: Time O(n log n) for the sort + O(n) scan; Space O(1) extra (O(n) if sort copies).

Edge cases / pitfalls. Empty/one interval -> 0; identical intervals; touching intervals not counted as overlap (>=); sorting by end with a subtraction comparator can overflow (use Integer.compare); negative coordinates; do not update end when skipping an interval.

Pattern & related. Greedy interval scheduling (sort by end). Related: Minimum Number of Arrows to Burst Balloons (452), Meeting Rooms (252), Maximum Length of Pair Chain (646), Weighted Job Scheduling (1235), Merge Intervals (56).

4. Meeting Rooms (Easy · 252, premium)

Problem statement. Given an array of meeting time intervals [start, end), determine whether a person can attend all meetings. Example: [[0,30],[5,10],[15,20]] -> false. [[7,10],[2,4]] -> true. Constraints: 0 <= n <= 10^4, 0 <= start < end <= 10^6.

How the interviewer asks / follow-ups.

• "Does any pair of scheduled batch jobs / maintenance windows / API-key validity periods conflict?", "validate a merchant's submitted settlement-window config has no overlap".
• Follow-ups: return the conflicting pair(s); how many conflicts; then immediately escalate to Meeting Rooms II (how many rooms); streaming - check on every insert with a TreeMap (floor/ceiling neighbor check, O(log n)).
• Evaluates: sort + adjacent comparison, strict vs non-strict boundary, quick warm-up for II.

Approach 1: Brute force. Compare all pairs: intervals i, j overlap iff max(start) < min(end). Time O(n^2), space O(1).

Approach 2: Sort by start + adjacent check (optimal). Key insight: after sorting by start, if any two meetings overlap then some adjacent pair overlaps (if i overlaps j > i+1, then i+1 starts before j and thus before i's end too). So compare each start with the previous end. Dry run [[0,30],[5,10],[15,20]]: sorted same. [5,10]: 5 < 30 -> conflict -> false.

Java code

static boolean canAttendMeetings(int[][] iv) {
    int[][] a = iv.clone();
    Arrays.sort(a, (x, y) -> Integer.compare(x[0], y[0]));
    for (int i = 1; i < a.length; i++)
        if (a[i][0] < a[i - 1][1]) return false;   // strict: back-to-back is fine
    return true;
}

Streaming variant: keep a TreeMap<Integer,Integer> start->end; on a new [s,e), check floorEntry(s) end <= s... and ceilingKey(s) start >= e, else conflict.

Complexity

• Brute force: Time O(n^2), Space O(1).
• Sort: Time O(n log n), Space O(1) extra (O(n) here due to the clone).

Edge cases / pitfalls. Empty array -> true; one meeting -> true; back-to-back [1,2],[2,3] -> true (< not <=); only checking adjacent before sorting is wrong; clarify half-open assumption.

Pattern & related. Sort + adjacent compare. Related: Meeting Rooms II (253), Merge Intervals (56), My Calendar I (729), Non-overlapping Intervals (435).

5. Meeting Rooms II (Medium · 253, premium)

Problem statement. Given an array of meeting time intervals, return the minimum number of conference rooms required. Example: [[0,30],[5,10],[15,20]] -> 2. [[7,10],[2,4]] -> 1. Constraints: 1 <= n <= 10^4, 0 <= start < end <= 10^6.

How the interviewer asks / follow-ups.

• "Given transaction start and end timestamps, what is the peak number of concurrent transactions / minimum number of servers or connection-pool size / minimum number of HSM slots?", "maximum simultaneous logged-in users", "minimum number of payment-gateway worker threads so no request waits".
• Follow-ups: also assign each meeting to a room (min-heap holds (end, roomId)); streaming events with unbounded input (maintain a min-heap of active end times; the answer is the max heap size); return the time of peak load; distributed logs - bucket by time then sweep; very large timestamps - coordinate compression or sweep with events; weighted concurrency (each transaction consumes w units) - sweep with +w/-w; limited rooms -> reject/queue.
• Evaluates: seeing it as "max overlap at any instant", three equivalent implementations, the tie-break (end at t frees the room for a meeting starting at t), complexity analysis.

Approach 1: Brute force. For each meeting start time t, count meetings active at t (start <= t < end); answer is the max. Time O(n^2), space O(1). (The max overlap always occurs at some meeting's start.)

Approach 2: Min-heap of end times. Sort meetings by start. Keep a min-heap of end times of rooms in use. For each meeting: if the earliest-ending room has end <= start, reuse it (poll); push the new end. Heap size at the end is the number of rooms (peak simultaneously used rooms never decreases below what we allocated, so final size = answer). Time O(n log n), space O(n).

Approach 3: Two sorted arrays / sweep (optimal in simplicity). Key insight: you do not need to know which meeting ends, only how many have ended. Sort starts and ends separately. Walk through the starts: if the current start >= the earliest unprocessed end, a room was freed -> advance the end pointer (reuse); otherwise a new room is needed. Dry run [[0,30],[5,10],[15,20]]: starts [0,5,15], ends [10,20,30]. start 0 < end 10 -> rooms=1. start 5 < 10 -> rooms=2. start 15 >= 10 -> reuse, j=1. rooms=2. Answer 2. Tie case [[1,5],[5,10]]: starts [1,5], ends [5,10]. start 1 < 5 -> rooms=1. start 5 >= 5 -> reuse. Answer 1 (need >=).

Approach 4: Sweep line with events (TreeMap of time -> delta). Process in time order, +1 at start, -1 at end; since the ordering at the same timestamp is by key and the net delta is merged, a meeting ending at t and one starting at t net out correctly. The max prefix sum is the answer. Best generalization for weighted concurrency and for reporting the peak time.

Java code

// Approach 3: two sorted arrays - O(n log n) time, O(n) space
static int minMeetingRooms(int[][] iv) {
    int n = iv.length;
    int[] st = new int[n], en = new int[n];
    for (int i = 0; i < n; i++) { st[i] = iv[i][0]; en[i] = iv[i][1]; }
    Arrays.sort(st);
    Arrays.sort(en);
    int rooms = 0, j = 0;                    // j = index of earliest not-yet-freed end
    for (int i = 0; i < n; i++) {
        if (st[i] >= en[j]) j++;             // some meeting finished: reuse its room
        else rooms++;                        // all current rooms busy: allocate
    }
    return rooms;
}

// Approach 2: min-heap of end times (extendable to room assignment)
static int minMeetingRoomsHeap(int[][] iv) {
    int[][] a = iv.clone();
    Arrays.sort(a, (x, y) -> Integer.compare(x[0], y[0]));
    PriorityQueue<Integer> ends = new PriorityQueue<>();
    for (int[] m : a) {
        if (!ends.isEmpty() && ends.peek() <= m[0]) ends.poll();  // free the earliest-ending room
        ends.add(m[1]);
    }
    return ends.size();
}

// Approach 4: sweep line over +1/-1 events (also gives peak time / weighted load)
static int minMeetingRoomsSweep(int[][] iv) {
    TreeMap<Integer, Integer> delta = new TreeMap<>();
    for (int[] m : iv) {
        delta.merge(m[0], 1, Integer::sum);
        delta.merge(m[1], -1, Integer::sum);   // same-timestamp +1/-1 net out: end frees before start takes
    }
    int cur = 0, best = 0;
    for (int v : delta.values()) { cur += v; best = Math.max(best, cur); }
    return best;
}

Why the two-array loop is right: rooms only grows when no meeting has ended by the time a new one starts, so rooms = (number of starts) - (number of ends consumed) = max concurrency; j never exceeds i because each end is after its own start.

Complexity

• Brute force: Time O(n^2), Space O(1).
• Min-heap: Time O(n log n) - sort plus n heap ops of O(log n); Space O(n) heap.
• Two arrays: Time O(n log n) for two sorts + O(n) pass; Space O(n).
• Sweep with TreeMap: Time O(n log n); Space O(n). With a plain array of size T (small, bounded time domain) it is O(n + T).

Edge cases / pitfalls. Empty input -> 0 (the arrays version returns 0 since loop skips; en[j] is never accessed); touching meetings share a room (>= / <=, not strict); all identical meetings -> n; one meeting contains many others -> 2 at most when disjoint inside; sorting the intervals as pairs but then comparing start with the wrong end; heap comparator on int[] with subtraction overflow; if the interviewer wants which room, use the heap with room ids.

Pattern & related. Sweep line / peak concurrency; min-heap of end times. Related: Meeting Rooms (252), Car Pooling (1094), My Calendar III (732), Minimum Number of Arrows (452), Task Scheduler (621), Maximum Number of Events (1353), Employee Free Time (759).