DSA Notes · chapter 09 · Java Live Code

Intervals become easy after you sort them. Merge asks for the union segments. Platforms / meeting rooms II asks for peak concurrency — how many are live at once. Those are different outputs on the same sort. Min arrows is a greedy count of groups, not a merged list.

09 · intervals

Sort by start, then either merge or count overlap

If they want the combined ranges, emit merged [start, end] pairs. If they want rooms or platforms, count the maximum number of open intervals. Confirm touching endpoints: does [1,2][2,3] merge, and does a departure at 10:00 free a platform for an arrival at 10:00?

Merge→ Platforms / rooms

Merge intervals

Recognize it from

A list of [start, end] ranges; return the union as disjoint intervals. Overlap or touch should become one interval (ask if touch merges). Unsorted input is the default. Not “how many rooms,” not “min arrows.”

What it actually does

After sorting by start, overlap is a local question against only the interval you are currently extending. If the next start is past the current end, emit the current interval and start a new one. Else stretch the current end to max(end, next.end).

The simple block assumes the input is already ordered so you can watch the compare. The interview block sorts with Integer.compare, clones so you do not mutate a shared array the caller still needs, and returns an empty array on empty input.

Simple — read this first

public int[][] mergeSorted(int[][] iv) {
    List<int[]> out = new ArrayList<>();
    int[] cur = iv[0];
    for (int i = 1; i < iv.length; i++) {
        if (iv[i][0] <= cur[1]) {
            // overlap or touch: the merged end is the farther one
            cur[1] = Math.max(cur[1], iv[i][1]);
        } else {
            out.add(cur);
            cur = iv[i];
        }
    }
    out.add(cur);
    return out.toArray(new int[0][]);
}

Interview — type this

public int[][] merge(int[][] iv) {
    if (iv == null || iv.length == 0) return new int[0][];
    Arrays.sort(iv, (a, b) -> Integer.compare(a[0], b[0]));
    List<int[]> out = new ArrayList<>();
    int[] cur = iv[0].clone(); // clone so later extend does not mutate the caller’s row
    for (int i = 1; i < iv.length; i++) {
        if (iv[i][0] <= cur[1]) {
            cur[1] = Math.max(cur[1], iv[i][1]);
        } else {
            out.add(cur);
            cur = iv[i].clone();
        }
    }
    out.add(cur);
    return out.toArray(new int[0][]);
}

Example 1 — simple

Input [1,3], [2,6]. One overlap.

1────3 2────────6 1──────────6

cur starts as [1,3]; next start 2 is ≤ 3
i	next	cur	next.start ≤ cur.end?	cur after
1	[2,6]	[1,3]	yes, 2 ≤ 3	[1,6]
end	—	[1,6]	emit	[1,6]

Answer [1,6].

Example 2 — every step

Input [1,3], [2,6], [8,10], [15,18]. Already sorted. Every compare, no skipped interval.

[1,3] [2,6] [8,10] [15,18]

Every next interval against the current cluster
i	next	cur before	compare	action	out
1	[2,6]	[1,3]	2 ≤ 3	extend end to 6	[]
2	[8,10]	[1,6]	8 > 6	emit [1,6], cur=[8,10]	[1,6]
3	[15,18]	[8,10]	15 > 10	emit [8,10], cur=[15,18]	[1,6], [8,10]
end	—	[15,18]	—	emit [15,18]	[1,6], [8,10], [15,18]

Answer [1,6], [8,10], [15,18]. If the second interval had been [2,4], the merge would still be [1,6] because you take max(end), not the later interval’s end blindly.

TC O(n log n) sort SC O(n) output

Why sort by start, not a heap After the sort, you only look at the last open interval. A heap of ends is the meeting-room twin — it answers concurrency, not the union. Pairwise merge-until-stable is O(n²).

Common mistakes

Sorting by end, then missing an overlap that starts late but sticks out.
Using < when they said touching ranges merge ([1,2][2,3] → [1,3]).
Forgetting to emit the last cur after the loop.

Notebook problems for this topic

Problem	Pattern	Links
Merge Intervals	Sort by start, extend or emit	Java in ch.05 · cheat card · clue
Min arrows to burst balloons	Sort by end, count groups — not a merged list	cheat card

Minimum platforms / Meeting Rooms II

Recognize it from

Trains with arrival[] and departure[], or meetings as [start, end] pairs. How many platforms / rooms so no two occupy the same one at the same time. Peak overlap, not the union of ranges.

What it actually does

Sweep: sort arrivals and departures separately. A two-pointer walk over the two sorted lists: if the next event is an arrival (arrival ≤ current departure), a new platform is taken; else a train left and you free one. Track the max of the running count. Confirm whether equal times need an extra platform (GFG often yes: arrival before departure when the clock matches).

Interview: you are handed [start, end] pairs. Sort by start. A min-heap of end times is the set of busy rooms. If the earliest end is already free, poll it, then offer the new end. Heap size at the end (or the max size along the way, same number if you poll only when free) is the answer.

Simple — read this first

public int minPlatforms(int[] arr, int[] dep) {
    Arrays.sort(arr);
    Arrays.sort(dep);
    int i = 0, j = 0, cur = 0, best = 0;
    while (i < arr.length) {
        if (arr[i] <= dep[j]) {
            // next event is an arrival (equal time still needs a platform here)
            cur++;
            best = Math.max(best, cur);
            i++;
        } else {
            cur--;
            j++;
        }
    }
    return best;
}

Interview — type this

public int minMeetingRooms(int[][] intervals) {
    if (intervals == null || intervals.length == 0) return 0;
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
    PriorityQueue<Integer> ends = new PriorityQueue<>();
    for (int[] iv : intervals) {
        // peek() < start reuses a room; ask if == start also reuses
        if (!ends.isEmpty() && ends.peek() < iv[0]) ends.poll();
        ends.offer(iv[1]);
    }
    return ends.size();
}

Example 1 — simple

Two meetings overlap: arrivals 900, 1000, departures 1100, 1200.

900────────1100 1000────────1200 need 2 platforms while both are in

Sweep — arrival vs departure pointer
arr[i]	dep[j]	compare	cur	best
900	1100	900 ≤ 1100 → arrive	1	1
1000	1100	1000 ≤ 1100 → arrive	2	2
(done)	1100	loop ends; both still in	2	2

Answer 2.

Example 2 — every step

Starts 900, 940, 950, ends 910, 1200, 1120. Sort ends to 910, 1120, 1200. Every pointer move.

arr sorted 900 940 950 dep sorted 910 1120 1200

i walks arrivals, j walks departures — every move
i	j	arr[i]	dep[j]	event	cur	best
0	0	900	910	900 ≤ 910 arrive, i→1	1	1
1	0	940	910	940 > 910 depart, j→1	0	1
1	1	940	1120	940 ≤ 1120 arrive, i→2	1	1
2	1	950	1120	950 ≤ 1120 arrive, i→3	2	2

Answer 2 — the 900–910 train is gone before 940, then 940–1200 and 950–1120 overlap. Heap of ends on the same pairs: offer 910; 940 > 910 so poll and offer 1200; 950 < 1200 so offer 1120; size 2.

TC O(n log n) SC sweep O(1) extra SC heap O(n)

Why sweep or a heap of ends You only need the earliest room to free, not a full conflict matrix. Merge-intervals is the wrong output: it would glue 940–1200 and 950–1120 into one range and hide that they need two rooms. Ask < vs <= for equal timestamps out loud.

Common mistakes

Sorting each [arr[i], dep[i]] pair as a unit and then scanning like merge — that answers union, not peak.
Forgetting to sort arrivals and departures separately for the two-pointer sweep.
Using a max-heap of ends; the room that frees first is the minimum end.

Notebook problems for this topic

Problem	Pattern	Links
Minimum platforms / Meeting Rooms II	Sweep two pointers, or min-heap of ends	Java in ch.05 · cheat card · clue

Sort by start, then either merge or count overlap

Merge intervals

Recognize it from

What it actually does

Example 1 — simple

Example 2 — every step

Notebook problems for this topic

Minimum platforms / Meeting Rooms II

Recognize it from

What it actually does

Example 1 — simple

Example 2 — every step

Notebook problems for this topic

See also on this chapter