CodeWithYash

Intermediate · Module 14 · Lesson 6

Scheduling

Select the next job by priority or availability.

15–25 min readLesson 82 of 123

Lesson 82 of 123

1d streak

Priority Queue Scheduling: Meeting Rooms & Task Execution

Priority queues are the gold standard for resource scheduling (CPU task scheduling, meeting room allocation). In Meeting Rooms II, a min-heap tracks the earliest room release times to determine the minimum conference rooms required.

MeetingRooms.java
// Minimum Meeting Rooms Required - O(n log n) time, O(n) space
public int minMeetingRooms(int[][] intervals) {
    if (intervals == null || intervals.length == 0) return 0;

    // 1. Sort meetings by start time
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

    // 2. Min-Heap stores the end times of active meetings
    PriorityQueue<Integer> endTimesHeap = new PriorityQueue<>();
    endTimesHeap.offer(intervals[0][1]);

    for (int i = 1; i < intervals.length; i++) {
        // If earliest meeting ended before current meeting starts, reuse room!
        if (intervals[i][0] >= endTimesHeap.peek()) {
            endTimesHeap.poll();
        }
        // Allocate/extend room with current meeting's end time
        endTimesHeap.offer(intervals[i][1]);
    }

    // Size of heap is the maximum number of simultaneous rooms needed
    return endTimesHeap.size();
}

Cost Model

Complexity & Trade-offs

Priority scheduling
O(n log n)
O(n)
The bound follows from the number of states visited and the work performed per transition.

When to use it

  • Top-k, streaming medians, scheduling, and best-first frontiers.
  • Repeated access to an extreme without fully sorting.
  • Merging sorted sources.

Common mistakes

  • Choosing the wrong heap direction for a bounded top-k set.
  • Assuming heap iteration is globally sorted.
  • Claiming bottom-up heap construction is O(n log n).

Practice prompts

  • Reproduce the worked Scheduling example without looking at the trace.
  • Change one input condition and explain whether the Scheduling invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.