Priority Queue

Today, let’s look at LeetCode problem 2462: Total Cost to Hire K Workers. The instructions are as follows: You are given a 0-indexed integer array costs where costs[i] is the cost of hiring the \(i\)-th worker. You are also given two integers \(k\) and candidates. We want to hire exactly \(k\) workers according to the following rules: You will run \(k\) sessions and hire exactly one worker in each session. In each hiring session, choose the worker with the lowest cost from either the first candidates workers or the last candidates workers. Break the tie by the smallest index. For example, if costs = [3,2,7,7,1,2] and candidates = 2, then in the first hiring session, we will choose the 4th worker because they have the lowest cost [3,2,7,7,**1**,2]. In the second hiring session, we will choose 1st worker because they have the same lowest cost as 4th worker but they have the smallest index [3,**2**,7,7,2]. Please note that the indexing may be changed in the process. If there are fewer than candidates workers remaining, choose the worker with the lowest cost among them. Break the tie by the smallest index. A worker can only be chosen once. Return the total cost to hire exactly \(k\) workers. ...

In this post, we’ll be solving LeetCode problem 2542. We have two integer arrays nums1 and nums2 with size \(n\), as well as an integer \(k\). Let’s denote nums1 with \(A\) and nums2 with \(B\). If we pick a set of indices \(S\) with exactly \(k\) elements, we obtain a score as follows: \[ \min \left\{ B_i | i \in S \right\} \sum_{i \in S} A_i \] There are many different sets \(S\) that give different scores. We want to find the maximum possible score. ...

In this post, we’ll be solving LeetCode problem 2236. We start with an infinite set containing all positive integers. We may remove and return the smallest integer using int popSmallest() or add a positive integer back into the set using void addBack(int num). Strategy If we only focus on popping smallest integers, then we only need to keep track of the smallest number in the set with a variable n. We start with n = 1. Each time we pop, we increment n by one. ...