DSA-039 · Active-end heap and peak concurrency

Meeting Rooms II — Resource Count

Intermediate · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 9341 deterministic checks. Learner drafts are not executed.

Understand the problem

Return the minimum number of identical rooms needed to host every positive-duration meeting.

meetings is a non-null int[][] with 0–100,000 signed-int [start,end] rows. Both methods throw IllegalArgumentException for null/malformed rows or start≥end; zero-duration meetings are rejected.
Meetings are half-open [start,end): a room is free at its ending instant and may host a meeting starting then. Every meeting needs one room for its entire interval; empty input returns zero.
Preserve caller order and row values. Return a count only. The optimized heap stores one end per currently active meeting, including duplicate ends. It does not store permanent room identities, and iterating a PriorityQueue is not a sorted traversal.

Examples

Input: [[0,30],[5,10],[15,20]]
Output: 2
The long meeting overlaps each short one, but the two short meetings can reuse one room.
Input: [[0,3],[0,3],[3,5],[3,5]]
Output: 2
Both rooms release at three before the two new meetings begin.

Before you start

Closed versus half-open intervals and compatible endpoints
Sorting with safe comparators and invariant or exchange proofs

Recognize the structure

The answer is the maximum number of simultaneous meetings. A min-heap lets a start-ordered scan expire every already-ended meeting, then measure the active count after the new meeting arrives.

Try before revealing

Hint 1

What quantity lower-bounds the number of rooms at an instant?

Hint 2

Which old meetings have ended before the next arrival?

Hint 3

Expire all end≤start, add the new end, and record peak heap size.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Rescan occupancy at every meeting start

For each candidate start t, count all rows with start≤t<end and retain the maximum. For [0,10),[2,3),[3,5), active counts at starts are 1,2,2. A concurrency maximum is attained at a start because counts only decrease at ends. This O(n²) baseline uses O(1) other state.

Improve the baseline

Process arrivals chronologically

Sort a cloned outer array by start. Previous meetings are the only ones that may still occupy rooms at the next start.

Release every compatible ending

While the minimum active end≤next.start, remove it. Use while because several meetings can have finished since the previous arrival.

Add and retain the peak

Insert the new end, then update peak from heap size. The final heap size can be smaller than the historical peak, so return peak rather than the number still active at the last start.

Why it is correct

Active-set invariant

After processing a meeting starting at t, the heap contains exactly the end times of all processed meetings whose end>t. Removed entries have ended, remaining entries still occupy time, and the newly added end is greater than t by validation.

Necessary lower bound

At any instant with c active meetings, at least c rooms are required. Recording the greatest active count therefore gives a lower bound on any feasible room allocation.

Sufficient upper bound

At a new start, ended rooms can be reused. If all previously used rooms are still busy, allocating one more creates exactly the new active count; otherwise an idle room suffices. Thus a schedule never needs more rooms than the peak. Each end enters and leaves the heap at most once, completing the scan.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.*;
public final class Solution {
    private static void validate(int[][] meetings) {
        for (int[] row : meetings) if (row == null || row.length != 2 || row[0] >= row[1]) throw new IllegalArgumentException("positive-length half-open meetings required");
    }
    public static int minMeetingRooms(int[][] meetings) {
        validate(meetings);
        int[][] sorted = meetings.clone();
        Arrays.sort(sorted, Comparator.comparingInt(value -> value[0]));
        PriorityQueue<Integer> activeEnds = new PriorityQueue<>();
        int peak = 0;
        for (int[] next : sorted) {
            while (!activeEnds.isEmpty() && activeEnds.peek() <= next[0]) activeEnds.remove();
            activeEnds.add(next[1]);
            peak = Math.max(peak, activeEnds.size());
        }
        return peak;
    }
    public static int baseline(int[][] meetings) {
        validate(meetings);
        int peak = 0;
        for (int[] candidate : meetings) {
            int active = 0;
            for (int[] row : meetings) if (row[0] <= candidate[0] && candidate[0] < row[1]) active++;
            peak = Math.max(peak, active);
        }
        return peak;
    }
}

Read the meaningful blocks

Release before insert

Half-open semantics requires ends at t to leave before starts at t contribute to concurrency.

Heap state means active meetings

Removing all finished ends keeps the state exact. An alternative heap of allocated room histories has a different invariant and must not be explained as this active set.

Sort only for display

The Java heap guarantees its minimum at peek, not sorted iteration. Walkthroughs display a separately sorted multiset of end values for readability.

Complexity

O(n log n) time for sorting and at most n heap insertions/removals; O(n) auxiliary storage for the copied order, sort workspace, and up to n simultaneous ends.

The start-occupancy baseline costs O(n²) time and O(1) other state. A sorted event sweep is another O(n log n) method; at equal timestamps process ends before starts or aggregate their net change under the same half-open rule.

Exact-state walkthroughs

Reveal normal and boundary traces

A released short meeting lets a room be reused

Input: [[0,30],[5,10],[15,20],[30,40]] · Result: 2

Step 1 of 9: Sort arrivals and start without occupied rooms.

Displayed end values are a sorted copy for readability, not Java PriorityQueue iteration order.

Half-open meeting coordinates — end excluded

Endpoint spacing is compressed to show coordinate order; bar lengths do not measure duration. Filled dots include an endpoint; an open right circle excludes it. Dashed vertical lines are fixed arrow positions.

Row #0: [0, 30)
Row #1: [5, 10)
Row #2: [15, 20)
Row #3: [30, 40)

Heap end-time multiset — sorted only for display

Empty at this step.

After insertion, these ends belong to currently active processed meetings. Historical peak: 0.

State after this step
Variable	Value
intervalRows	`[[0,30],[5,10],[15,20],[30,40]]`
index	`-1`
phase	`"initial"`
activeEndValues	`[]`
peak	`0`
closed	`false`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static void validate(int[][] meetings) {
 4         for (int[] row : meetings) if (row == null || row.length != 2 || row[0] >= row[1]) throw new IllegalArgumentException("positive-length half-open meetings required");
 5     }
 6     public static int minMeetingRooms(int[][] meetings) {
 7         validate(meetings);
 8         int[][] sorted = meetings.clone();
 9         Arrays.sort(sorted, Comparator.comparingInt(value -> value[0]));
10         PriorityQueue<Integer> activeEnds = new PriorityQueue<>();
11         int peak = 0;
12         for (int[] next : sorted) {
13             while (!activeEnds.isEmpty() && activeEnds.peek() <= next[0]) activeEnds.remove();
14             activeEnds.add(next[1]);
15             peak = Math.max(peak, activeEnds.size());
16         }
17         return peak;
18     }
19     public static int baseline(int[][] meetings) {
20         validate(meetings);
21         int peak = 0;
22         for (int[] candidate : meetings) {
23             int active = 0;
24             for (int[] row : meetings) if (row[0] <= candidate[0] && candidate[0] < row[1]) active++;
25             peak = Math.max(peak, active);
26         }
27         return peak;
28     }
29 }
30

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Sort arrivals and start without occupied rooms.
Displayed end values are a sorted copy for readability, not Java PriorityQueue iteration order.
intervalRows
[[0,30],[5,10],[15,20],[30,40]]
index
-1
phase
"initial"
activeEndValues
[]
peak
0
closed
false
Insert this end and record peak occupancy.
The heap now represents exactly active processed meetings; the historical peak is the required room count.
intervalRows
[[0,30],[5,10],[15,20],[30,40]]
index
0
phase
"insert"
activeEndValues
[30]
peak
1
closed
false
currentStart
0
currentEnd
30
Insert this end and record peak occupancy.
The heap now represents exactly active processed meetings; the historical peak is the required room count.
intervalRows
[[0,30],[5,10],[15,20],[30,40]]
index
1
phase
"insert"
activeEndValues
[10,30]
peak
2
closed
false
currentStart
5
currentEnd
10
Release one meeting that ended at or before this arrival.
Release continues until every remaining processed meeting is still active at this start. Half-open equality frees a room.
intervalRows
[[0,30],[5,10],[15,20],[30,40]]
index
2
phase
"release"
activeEndValues
[30]
peak
2
closed
false
currentStart
15
releasedEnd
10
Insert this end and record peak occupancy.
The heap now represents exactly active processed meetings; the historical peak is the required room count.
intervalRows
[[0,30],[5,10],[15,20],[30,40]]
index
2
phase
"insert"
activeEndValues
[20,30]
peak
2
closed
false
currentStart
15
currentEnd
20
Release one meeting that ended at or before this arrival.
Release continues until every remaining processed meeting is still active at this start. Half-open equality frees a room.
intervalRows
[[0,30],[5,10],[15,20],[30,40]]
index
3
phase
"release"
activeEndValues
[30]
peak
2
closed
false
currentStart
30
releasedEnd
20
Release one meeting that ended at or before this arrival.
Release continues until every remaining processed meeting is still active at this start. Half-open equality frees a room.
intervalRows
[[0,30],[5,10],[15,20],[30,40]]
index
3
phase
"release"
activeEndValues
[]
peak
2
closed
false
currentStart
30
releasedEnd
30
Insert this end and record peak occupancy.
The heap now represents exactly active processed meetings; the historical peak is the required room count.
intervalRows
[[0,30],[5,10],[15,20],[30,40]]
index
3
phase
"insert"
activeEndValues
[40]
peak
2
closed
false
currentStart
30
currentEnd
40
Return the contract result.
The result satisfies the stated objective, endpoint policy, and input-preservation contract.
result
2

Several rooms release at the same instant

Input: [[0,3],[0,3],[3,5],[3,5]] · Result: 2

Step 1 of 8: Sort arrivals and start without occupied rooms.

Displayed end values are a sorted copy for readability, not Java PriorityQueue iteration order.

Half-open meeting coordinates — end excluded

Row #0: [0, 3)
Row #1: [0, 3)
Row #2: [3, 5)
Row #3: [3, 5)

Heap end-time multiset — sorted only for display

Empty at this step.

After insertion, these ends belong to currently active processed meetings. Historical peak: 0.

State after this step
Variable	Value
intervalRows	`[[0,3],[0,3],[3,5],[3,5]]`
index	`-1`
phase	`"initial"`
activeEndValues	`[]`
peak	`0`
closed	`false`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static void validate(int[][] meetings) {
 4         for (int[] row : meetings) if (row == null || row.length != 2 || row[0] >= row[1]) throw new IllegalArgumentException("positive-length half-open meetings required");
 5     }
 6     public static int minMeetingRooms(int[][] meetings) {
 7         validate(meetings);
 8         int[][] sorted = meetings.clone();
 9         Arrays.sort(sorted, Comparator.comparingInt(value -> value[0]));
10         PriorityQueue<Integer> activeEnds = new PriorityQueue<>();
11         int peak = 0;
12         for (int[] next : sorted) {
13             while (!activeEnds.isEmpty() && activeEnds.peek() <= next[0]) activeEnds.remove();
14             activeEnds.add(next[1]);
15             peak = Math.max(peak, activeEnds.size());
16         }
17         return peak;
18     }
19     public static int baseline(int[][] meetings) {
20         validate(meetings);
21         int peak = 0;
22         for (int[] candidate : meetings) {
23             int active = 0;
24             for (int[] row : meetings) if (row[0] <= candidate[0] && candidate[0] < row[1]) active++;
25             peak = Math.max(peak, active);
26         }
27         return peak;
28     }
29 }
30

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Sort arrivals and start without occupied rooms.
Displayed end values are a sorted copy for readability, not Java PriorityQueue iteration order.
intervalRows
[[0,3],[0,3],[3,5],[3,5]]
index
-1
phase
"initial"
activeEndValues
[]
peak
0
closed
false
Insert this end and record peak occupancy.
The heap now represents exactly active processed meetings; the historical peak is the required room count.
intervalRows
[[0,3],[0,3],[3,5],[3,5]]
index
0
phase
"insert"
activeEndValues
[3]
peak
1
closed
false
currentStart
0
currentEnd
3
Insert this end and record peak occupancy.
The heap now represents exactly active processed meetings; the historical peak is the required room count.
intervalRows
[[0,3],[0,3],[3,5],[3,5]]
index
1
phase
"insert"
activeEndValues
[3,3]
peak
2
closed
false
currentStart
0
currentEnd
3
Release one meeting that ended at or before this arrival.
Release continues until every remaining processed meeting is still active at this start. Half-open equality frees a room.
intervalRows
[[0,3],[0,3],[3,5],[3,5]]
index
2
phase
"release"
activeEndValues
[3]
peak
2
closed
false
currentStart
3
releasedEnd
3
Release one meeting that ended at or before this arrival.
Release continues until every remaining processed meeting is still active at this start. Half-open equality frees a room.
intervalRows
[[0,3],[0,3],[3,5],[3,5]]
index
2
phase
"release"
activeEndValues
[]
peak
2
closed
false
currentStart
3
releasedEnd
3
Insert this end and record peak occupancy.
The heap now represents exactly active processed meetings; the historical peak is the required room count.
intervalRows
[[0,3],[0,3],[3,5],[3,5]]
index
2
phase
"insert"
activeEndValues
[5]
peak
2
closed
false
currentStart
3
currentEnd
5
Insert this end and record peak occupancy.
The heap now represents exactly active processed meetings; the historical peak is the required room count.
intervalRows
[[0,3],[0,3],[3,5],[3,5]]
index
3
phase
"insert"
activeEndValues
[5,5]
peak
2
closed
false
currentStart
3
currentEnd
5
Return the contract result.
The result satisfies the stated objective, endpoint policy, and input-preservation contract.
result
2

Test the contract

Input: []
Output: 0
No room is required.
Input: [[0,2],[2,4]]
Output: 1
Immediate room reuse.
Input: [[1,5],[1,5],[1,5]]
Output: 3
Three separate simultaneous occurrences.
Input: [[2,2]]
Output: IllegalArgumentException
Zero-duration meetings are rejected.

Common mistakes and counterexamples

Insert before releasing equal-time ends

Counterexample: [0,3) and [3,5) need one room, not two.

Release every end≤the new start first.

Return the final active count

Counterexample: [[0,10],[0,10],[20,30]] has peak two but only one active at the final start.

Retain and return the maximum.

Treat heap iteration as sorted

Counterexample: PriorityQueue iteration may expose an internal heap arrangement.

Use peek for the minimum and a sorted copy only when presenting a readable multiset.

Follow-ups

Return room assignments.

Store (end,roomId) for busy rooms and a pool of released IDs. Assign a free ID when possible, allocate a new one otherwise, and retain original meeting indices for the result.

Use a sweep instead.

Sort starts and ends or aggregate endpoint deltas. Explain equal-time tie rules and prove the maximum running occupancy equals the room requirement; do not mix closed-balloon endpoints into this half-open model.

Give each meeting a capacity demand.

If rooms provide divisible capacity, sweep weighted start/end deltas. If each meeting needs several indivisible resources with compatibility restrictions, peak total demand may no longer solve the assignment problem without extra assumptions.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 143/20,000 characters

Self-review

I define exactly what each heap entry represents.I release before equal-time arrivals.I prove both lower and upper room bounds.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-16 · Original teaching content, examples, and Java implementations authored for AceYourInterviews. These standard algorithmic tasks carry no company-frequency or interview-outcome claims.