Fundamentals/Patterns/Greedy + Heap9 problems· Greedy

Use heap to always pick the optimal element greedily

When to useTask scheduler, reorganize string, connect ropes, minimum cost merge

iterative
Connect Ropes
connect_ropes
Find The Highest Profit
find_the_highest_profit
Five Star Seller
five_star_sellers
Merge K Sorted Lists
merge_k_sorted_lists
Multiprocessor System
multiprocessor_system
Reorganize String
reorganize_string
Kth Smallest Element in a Sorted Matrix
kth_smallest_element_in_a_sorted_matrix
Longest String Without 3 Consecutive Characters
longest_string_without_3_consecutive_characters
Meeting Rooms IImedium
meeting_rooms_ii · no slots
INITIALIZE
insert all elements into heap (max or min)
const heap = new MinHeap();
for (const r of ropes) heap.push(r);
let cost = 0;
const heap = new MaxHeap();
for (const inv of inventories) heap.push(inv);
let profit = 0;
const heap = new MaxHeap(); // keyed by marginal gain
let sum = 0;
for (const [five, total] of productRatings) {
sum += five / total;
heap.push([gain(five, total), five, total]);
}
const heap = new MinHeap();
for (let i = 0; i < lists.length; i++) {
if (lists[i].length > 0) heap.push([lists[i][0], i, 0]);
}
const result = [];
const heap = new MaxHeap();
for (const power of processorPower) heap.push(power);
let hours = 0;
let remaining = tasks;
const counts = new Map();
for (const ch of s) counts.set(ch, (counts.get(ch) ?? 0) + 1);
const heap = new MinHeap((a, b) => b[1] - a[1]);
for (const [ch, c] of counts) {
if (c > Math.ceil(s.length / 2)) return '';
heap.push([ch, c]);
}
let result = ''; let prev = null;
const heap = new MinHeap();
heap.push({ priority: matrix[0][0], row: 0, col: 0 });
const columnTop = Array(n).fill(0);
const rowFirst = Array(n).fill(0);
const heap = new MaxHeap();
if (a > 0) heap.push([a, 'a']);
if (b > 0) heap.push([b, 'b']);
if (c > 0) heap.push([c, 'c']);
let result = '';
TRAVERSE
while heap not empty (or size > 1)
while (heap.size() > 1) {
for (let i = 0; i < order; i++) {
while (sum < target) {
while (heap.size() > 0) {
while (remaining > 0) {
while (heap.size() > 0) {
while (k > 1) {
while (heap.size() > 0) {
pop optimal
pop optimal element(s) from heap
const a = heap.pop();
const b = heap.pop();
const top = heap.pop();
const [, five, total] = heap.pop();
const [value, listIndex, elemIndex] = heap.pop();
const top = heap.pop();
const [ch, c] = heap.pop();
k--;
const { row, col } = heap.pop();
const [count1, ch1] = heap.pop();
[COMPUTE]
compute step contribution to result
cost += a + b;
profit += top;
sum += gain(five, total);
needed++;
result.push(value);
remaining -= top;
hours += 1;
result += ch;
// unlock right neighbor if its column frontier has reached this row
if (col + 1 < n && columnTop[col + 1] === row)
heap.push({ priority: matrix[row][col+1], row, col: col+1 });
// unlock down neighbor if its row frontier has reached this col
if (row + 1 < n && rowFirst[row + 1] === col)
heap.push({ priority: matrix[row+1][col], row: row+1, col });
rowFirst[row] = col + 1;
columnTop[col] = row + 1;
if (last two chars === ch1) {
// pop second-best, place it instead, push ch1 back
const [count2, ch2] = heap.pop();
result += ch2;
heap.push([count2 - 1, ch2]);
heap.push([count1, ch1]);
} else {
result += ch1;
heap.push([count1 - 1, ch1]);
}
reinsert
push back any modified element if applicable
heap.push(a + b);
heap.push(top - 1);
heap.push([gain(five+1, total+1), five+1, total+1]);
if (elemIndex + 1 < lists[listIndex].length)
heap.push([lists[listIndex][elemIndex + 1], listIndex, elemIndex + 1]);
heap.push(Math.floor(top / 2));
if (prev !== null && prev[1] > 0) heap.push(prev);
prev = [ch, c - 1];
RETURN
return result
return cost;
return profit;
return needed;
return result;
return hours;
return result;
return heap.peek().priority;
return result;