# Heap and priority queue in Python

## Intro

In Python, “heapq” module is available to use. Whenever elements are pushed or popped, heap structure is maintained. The heap[0] element also returns the smallest element each time.

## [Leetcode 857] Minimum Cost to Hire K Workers

There are n workers. You are given two integer arrays quality and wage where quality[i] is the quality of the ith worker and wage[i] is the minimum wage expectation for the ith worker.

We want to hire exactly k workers to form a paid group. To hire a group of k workers, we must pay them according to the following rules:

- Every worker in the paid group should be paid in the ratio of their quality compared to other workers in the paid group.
- Every worker in the paid group must be paid at least their minimum wage expectation.

Given the integer k, return the least amount of money needed to form a paid group satisfying the above conditions. Answers within 10-5 of the actual answer will be accepted.

Example 1:

1 | Input: quality = [10,20,5], wage = [70,50,30], k = 2 |

Example 2:

1 | Input: quality = [3,1,10,10,1], wage = [4,8,2,2,7], k = 3 |

Constraints:

- n == quality.length == wage.length
- 1 <= k <= n <= 104
- 1 <= quality[i], wage[i] <= 104

Solution:

1 | class Solution: |

## [Leetcode 1383] Maximum Performance of a Team

You are given two integers n and k and two integer arrays speed and efficiency both of length n. There are n engineers numbered from 1 to n. speed[i] and efficiency[i] represent the speed and efficiency of the ith engineer respectively.

Choose at most k different engineers out of the n engineers to form a team with the maximum performance.

The performance of a team is the sum of its engineers’ speeds multiplied by the minimum efficiency among its engineers.

Return the maximum performance of this team. Since the answer can be a huge number, return it modulo 109 + 7.

Example 1:

1 | Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2 |

Example 2:

1 | Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3 |

Example 3:

1 | Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4 |

Constraints:

- 1 <= k <= n <= 105
- speed.length == n
- efficiency.length == n
- 1 <= speed[i] <= 105
- 1 <= efficiency[i] <= 108

Solution:

1 | class Solution: |

## [Leetcode 2462] Total Cost to Hire K Workers

You are given a 0-indexed integer array costs where costs[i] is the cost of hiring the ith 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(instead, read candidates as n to make it easier understand) 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.

Example 1:

1 | Input: costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4 |

Example 2:

1 | Input: costs = [1,2,4,1], k = 3, candidates = 3 |

Constraints:

- 1 <= costs.length <= 105
- 1 <= costs[i] <= 105
- 1 <= k, candidates <= costs.length

Solution:

1 | class Solution: |

## [Leetcode 2542] Maximum Subsequence Score

You are given two 0-indexed integer arrays nums1 and nums2 of equal length n and a positive integer k. You must choose a subsequence of indices from nums1 of length k.

For chosen indices i0, i1, …, ik - 1, your score is defined as:

- The sum of the selected elements from nums1 multiplied with the minimum of the selected elements from nums2.
- It can defined simply as: (nums1[i0] + nums1[i1] +…+ nums1[ik - 1]) * min(nums2[i0] , nums2[i1], … ,nums2[ik - 1]).

Return the maximum possible score.

A subsequence of indices of an array is a set that can be derived from the set {0, 1, …, n-1} by deleting some or no elements.

Example 1:

1 | Input: nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3 |

Constraints:

- n == nums1.length == nums2.length
- 1 <= n <= 105
- 0 <= nums1[i], nums2[j] <= 105
- 1 <= k <= n

Solution:

1 | class Solution: |