Heap for Scheduling: Task Execution and Resource Allocation

Meeting Rooms II (LeetCode 253)

Find the minimum number of meeting rooms required (equivalent to the maximum number of overlapping intervals at any given time).

Approach: Min Heap

public int minMeetingRooms(int[][] intervals) {
    if (intervals == null || intervals.length == 0) return 0;
    
    // Sort meetings by start time
    Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
    
    // Min Heap to store end times of currently active meetings
    PriorityQueue<Integer> endTimes = new PriorityQueue<>();
    
    for (int[] interval : intervals) {
        // If the earliest ending meeting is finished before the current one starts, reuse the room
        if (!endTimes.isEmpty() && endTimes.peek() <= interval[0]) {
            endTimes.poll();
        }
        // Always add the current meeting's end time
        endTimes.offer(interval[1]);
    }
    
    // The number of active rooms corresponds to the heap size
    return endTimes.size();
}

CPU Task Scheduler (LeetCode 621)

Calculate the shortest time to execute all tasks given a cooling period n between identical tasks.

Approach 1: Mathematical Optimization (Optimal O(N))

Focus on the task with the highest frequency.

public int leastInterval(char[] tasks, int n) {
    int[] frequencies = new int[26];
    for (char t : tasks) frequencies[t - 'A']++;
    Arrays.sort(frequencies);
    
    int maxFreq = frequencies[25];
    int idleSlots = (maxFreq - 1) * n;
    
    // Fill idle slots with other tasks
    for (int i = 24; i >= 0 && frequencies[i] > 0; i--) {
        idleSlots -= Math.min(frequencies[i], maxFreq - 1);
    }
    
    return tasks.length + Math.max(0, idleSlots);
}

Approach 2: Greedy Simulation with Max Heap

public int leastIntervalSimulation(char[] tasks, int n) {
    int[] freqs = new int[26];
    for (char t : tasks) freqs[t - 'A']++;
    
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    for (int f : freqs) if (f > 0) maxHeap.offer(f);
    
    int totalTime = 0;
    while (!maxHeap.isEmpty()) {
        List<Integer> tempStorage = new ArrayList<>();
        int cycleSize = n + 1; // Number of slots available in one cooling cycle
        
        while (cycleSize > 0 && !maxHeap.isEmpty()) {
            int remainingFreq = maxHeap.poll() - 1;
            if (remainingFreq > 0) tempStorage.add(remainingFreq);
            totalTime++;
            cycleSize--;
        }
        
        maxHeap.addAll(tempStorage);
        // If we still have tasks left but the cycle isn't full, add actual idle time
        if (!maxHeap.isEmpty()) {
            totalTime += cycleSize;
        }
    }
    return totalTime;
}

Reorganize String (LeetCode 767)

Rearrange string so that no two adjacent characters are the same. If the most frequent character appears more than (n+1)/2 times, it's impossible.

public String reorganizeString(String s) {
    int[] counts = new int[26];
    for (char c : s.toCharArray()) counts[c - 'a']++;
    
    // Max Heap based on character frequency
    PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[1] - a[1]);
    for (int i = 0; i < 26; i++) {
        if (counts[i] > 0) maxHeap.offer(new int[]{i, counts[i]});
    }
    
    StringBuilder sb = new StringBuilder();
    while (maxHeap.size() >= 2) {
        int[] first = maxHeap.poll();
        int[] second = maxHeap.poll();
        
        sb.append((char)('a' + first[0]));
        sb.append((char)('a' + second[0]));
        
        if (--first[1] > 0) maxHeap.offer(first);
        if (--second[1] > 0) maxHeap.offer(second);
    }
    
    // Handle potential last character
    if (!maxHeap.isEmpty()) {
        int[] last = maxHeap.poll();
        if (last[1] > 1) return ""; // Impossible to separate
        sb.append((char)('a' + last[0]));
    }
    return sb.toString();
}

Summary Table