# Heap

####

#### [253. Meeting Rooms II](https://leetcode.com/problems/meeting-rooms-ii/)

[link](/decode-leetcode/array/interval.md#1229-meeting-scheduler)

#### [1094. Car Pooling](https://leetcode.com/problems/car-pooling/)

[link](/decode-leetcode/array/interval.md#1094-car-pooling)

#### [846. Hand of Straights](https://leetcode.com/problems/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)* 

```java
    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

```java
    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](https://leetcode.com/problems/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.

```java
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](https://leetcode.com/problems/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.

```java
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](https://leetcode.com/problems/sort-characters-by-frequency/)

```java
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](https://leetcode.com/problems/find-median-from-data-stream/)

Use minHeap and maxHeap to store numbers.&#x20;

* 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.

```java
    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](https://leetcode.com/problems/the-skyline-problem/)

```java
    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](https://leetcode.com/problems/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.

&#x20; cost\[i]  / cost\[j]   =   quality\[i] / quality\[j]&#x20;

&#x20; 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.

```java
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](https://leetcode.com/problems/single-threaded-cpu/)

```java
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](https://leetcode.com/problems/maximize-ysum-by-picking-a-triplet-of-distinct-xvalues/)

```java
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;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://howardyangemail.gitbook.io/decode-leetcode/heap.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.