Heap

253. Meeting Rooms II

link

1094. Car Pooling

link

846. Hand of Straights

Add all cards to PQ, poll a card as the start, check if there is number can make a straight. Remove from PQ. If no such card, return false.

T: O(n*logn) . S: O(n)

    public boolean isNStraightHand(int[] hand, int W) {
        if (hand == null || hand.length == 0) {
            return false;
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int n : hand) {
            pq.add(n);
        }
        while (!pq.isEmpty()) {
            int start = pq.poll();
            for (int i = 1; i < W; i++) {
                if (!pq.remove(start + i)) {
                   return false;
                }
            }
        }
        return true;
    }

373. Find K Pairs with Smallest Sums

    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) {
            return new ArrayList<>();
        }
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
            @Override
            public int compare(int[] num1, int[] num2) {
                int sum1 = num1[0] + num1[1];
                int sum2 = num2[0] + num2[1];
                return Integer.compare(sum1, sum2);
            }
        });
        for (int i = 0; i < nums1.length; i++) {
            pq.offer(new int[]{nums1[i], nums2[0], 0});
        }
        List<List<Integer>> list = new ArrayList<>();
        while (!pq.isEmpty() && k-- > 0) {
            int[] curt = pq.poll();
            List<Integer> temp = new ArrayList<>();
            temp.add(curt[0]);
            temp.add(curt[1]);
            list.add(temp);
            int j = curt[2];
            if (j + 1 < nums2.length) {
                pq.offer(new int[]{curt[0], nums2[j + 1], j + 1});
            }
        }
        return list;
    }

659. Split Array into Consecutive Subsequences

Loop over the numbers, save existing consecutive arrays as range into PQ. Poll pq until find the range can connects to the current number. Start a new range if PQ is empty or pq.peek().end == n (eg.[1,2,3],[3,4,5]). Otherwise connect the range into a longer range.

public boolean isPossible(int[] nums) {
    PriorityQueue<Range> pq = new PriorityQueue<>((o1,o2) -> {
        if (o1.end == o2.end) {
            return o1.range - o2.range;
        }
        return o1.end - o2.end;
    });
    for (int n : nums) {
        while (!pq.isEmpty() && pq.peek().end + 1 < n) {
            if (pq.poll().range < 3) return false;
        }
        if (pq.isEmpty() || pq.peek().end == n) {
            pq.offer(new Range(n, n));
        } else {
            pq.offer(new Range(pq.poll().start, n));
        }
    }
    while (!pq.isEmpty()) {
        if (pq.poll().range < 3) return false;
    }
    return true;
}

class Range {
    int start, end, range;
    Range(int s, int e) {
        this.start = s;
        this.end = e;
        this.range = e - s + 1;
    }
}

358. Rearrange String k Distance Apart

Add all character counts to a maxHeap. Use a separate queue to keep k distance. As pq pops curt, append the char to sb, reduce the count, and add to queue. When queue.size() >= k, it means that the characters keep at least k distance. Put back the values back in maxHeap one by one, like sliding window.

public String rearrangeString(String s, int k) {
    int[] counts = new int[26];
    for (char c : s.toCharArray()) {
        counts[c - 'a']++;
    }
    PriorityQueue<Pair> pq = new PriorityQueue<>((o1,o2)->(o2.count - o1.count));
    for (char c = 'a'; c <= 'z'; c++) {
        if (counts[c - 'a'] != 0) pq.offer(new Pair(c, counts[c - 'a']));
    }
    Queue<Pair> q = new LinkedList<>();
    StringBuilder sb = new StringBuilder();
    while (!pq.isEmpty()) {
        Pair curt = pq.poll();
        sb.append(curt.c);
        curt.count--;
        q.offer(curt);
        if (q.size() >= k) {
            Pair poll = q.poll();
            if (poll.count != 0) pq.offer(poll);
        }
    }
    return sb.length() == s.length() ? sb.toString() : "";
}

class Pair {
    char c;
    int count;
    Pair(char c, int count) {
        this.c = c;
        this.count = count;
    }
}

451. Sort Characters By Frequency

public String frequencySort(String s) {
    Map<Character, Integer> map = new HashMap<>();
    for (char c : s.toCharArray()) {
        map.put(c, map.getOrDefault(c, 0) + 1);
    }
    PriorityQueue<Map.Entry<Character,Integer>> pq 
        = new PriorityQueue<>((o1,o2) -> (o2.getValue() - o1.getValue()));
    for (Map.Entry<Character,Integer> e : map.entrySet()) {
        pq.add(e);
    }
    StringBuilder sb = new StringBuilder();
    while (!pq.isEmpty()) {
        Map.Entry<Character,Integer> curt = pq.poll();
        while (curt.getValue() > 0) {
            sb.append(curt.getKey());
            curt.setValue(curt.getValue() - 1);
        }
    }
    return sb.toString();
}

295. Find Median from Data Stream

Use minHeap and maxHeap to store numbers.

• addNum: if size of two heap equal, add to minHeap, pop one from minHeap and add to maxHeap. Otherwise, add to maxHeap, pop one to minHeap.

• findMedian: If sizes of two heaps equal, return an average from peek of both heaps. Otherwise return from the larger heap.

    PriorityQueue<Integer> minHeap;
    PriorityQueue<Integer> maxHeap;
    public MedianFinder() {
        this.minHeap = new PriorityQueue<>();
        this.maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
    }

    public void addNum(int num) {
        if (minHeap.size() == maxHeap.size()){
            minHeap.add(num);
            maxHeap.offer(minHeap.poll());
        } else {
            maxHeap.add(num);
            minHeap.offer(maxHeap.poll());
        }
    }

    public double findMedian() {
        if (minHeap.size() > maxHeap.size()) return (double) minHeap.peek();
        else if (minHeap.size() < maxHeap.size()) return (double) maxHeap.peek();
        return ((double) minHeap.peek() + (double) maxHeap.peek()) / 2.0;
    }

218. The Skyline Problem

    public List<List<Integer>> getSkyline(int[][] buildings) {
        List<List<Integer>> res = new ArrayList<>();
        List<int[]> height = new ArrayList<>();     // height list to store all buildings' heights
        for (int[] b : buildings) {
            height.add(new int[]{b[0], - b[2]});    // start of a building, height stored as negtive
            height.add(new int[]{b[1], b[2]});      // end of a building, height stored as positive
        }
        Collections.sort(height, (a, b) -> (a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]));     // sort the height list
        
        // a pq that stores all the encountered buildings' heights in descending order
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> (b - a));
        pq.offer(0);
        int preMax = 0;
        
        for (int[] h : height) {
            if (h[1] < 0) {     // h[1] < 0, that means it meets a new building, so add it to pq
                pq.offer(-h[1]);
            } else {            // h[1] >=0, that means it has reached the end of the building, so remove it from pq
                pq.remove(h[1]);
            }
            
            // the current max height in all encountered buildings
            int curMax = pq.peek();
            // if the max height is different from the previous one, that means a critical point is met, add to result list
            if (curMax != preMax) {
                res.add(Arrays.asList(h[0], curMax));
                preMax = curMax;
            }
        }
        return res;
    }

857. Minimum Cost to Hire K Workers

Every worker in the paid group should be paid in the ratio of their quality compared to other workers in the paid group.

cost[i] / cost[j] = quality[i] / quality[j]

cost[i] / total cost = quality[i] / total quality

Which means a group of workers share the same "cost[i] / quality[i]", let's call it PAID_RATIO:

PAID_RATIO = total cost / total quality

Sort the workers by paid ratio so that you have the most "efficient worker" (perform best quality and least pay), use maxHeap to and poll the most "inefficient worker" when the total number workers in the group is larger than K. Update the min cost with the updated PAID_RATIO.

public double mincostToHireWorkers(int[] quality, int[] wage, int K) {
    Worker[] workers = new Worker[quality.length];
    for (int i = 0; i < quality.length; i++) {
        workers[i] = new Worker(quality[i], wage[i]);
    }
    Arrays.sort(workers, new Comparator<Worker>(){
        public int compare(Worker w1, Worker w2) {
            return Double.compare(w1.ratio, w2.ratio);
        }
    });
    PriorityQueue<Worker> pq = new PriorityQueue<>(new Comparator<Worker>(){
        public int compare(Worker w1, Worker w2) {
            return w2.quality - w1.quality;
        }
    });
    int totalQuality = 0;
    double min = Integer.MAX_VALUE; 
    for (Worker w : workers) {
        if (pq.size() >= K) {
            Worker poll = pq.poll();
            totalQuality -= poll.quality;
        }
        pq.offer(w);
        totalQuality += w.quality;
        if (pq.size() == K) {
            min = Math.min(min, totalQuality * w.ratio);
        }
    }
    return min;
}

class Worker {
    int quality;
    int wage;
    double ratio;
    Worker(int q, int w) {
        this.quality = q;
        this.wage = w;
        ratio = (double) w / q;
    }
}

1834. Single-Threaded CPU

import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public int[] getOrder(int[][] tasks) {
        int n = tasks.length;
        int[] result = new int[n];
        int[][] extendedTasks = new int[n][3];

        // extendedTasks[i] = [originalIndex, enqueueTime, processingTime]
        for (int i = 0; i < n; i++) {
            extendedTasks[i][0] = i;
            extendedTasks[i][1] = tasks[i][0];
            extendedTasks[i][2] = tasks[i][1];
        }

        // Sort by enqueue time
        Arrays.sort(extendedTasks, (a, b) -> Integer.compare(a[1], b[1]));

        // Min-heap ordered by processing time, then original index
        PriorityQueue<int[]> pq = new PriorityQueue<>(
            (a, b) -> a[2] == b[2] ? Integer.compare(a[0], b[0]) : Integer.compare(a[2], b[2])
        );

        int time = 0;
        int taskIndex = 0;   // Tracks how many tasks have been processed
        int enqueueIndex = 0; // Tracks tasks added to the queue

        while (taskIndex < n) {
            // Add all tasks that have become available by 'time'
            while (enqueueIndex < n && extendedTasks[enqueueIndex][1] <= time) {
                pq.offer(extendedTasks[enqueueIndex++]);
            }

            if (pq.isEmpty()) {
                // If no tasks available, fast-forward time to next enqueue
                time = extendedTasks[enqueueIndex][1];
                continue;
            }

            int[] currentTask = pq.poll();
            result[taskIndex++] = currentTask[0];
            time += currentTask[2];
        }

        return result;
    }
}

3572. Maximize Y‑Sum by Picking a Triplet of Distinct X‑Values

class Solution {
    public int maxSumDistinctTriplet(int[] x, int[] y) {
       Map<Integer, Integer> map = new HashMap<>(); // distinct x value, max in y
        for (int i = 0; i < x.length; i++) {
            int val = map.getOrDefault(x[i], Integer.MIN_VALUE);
            map.put(x[i], Math.max(val, y[i]));
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> (b - a));

        for (int val : map.values()) { // Fixed: values() instead of valueSet()
            pq.offer(val);
        }
        if (pq.size() < 3) return -1;
        int sum = 0;
        for (int i = 0; i < 3; i++) sum += pq.poll();
        return sum;
    }
}