Maximum Performance of a Team

Description

There are n engineers numbered from 1 to n and two arrays: speed and efficiency, where speed[i] and efficiency[i] represent the speed and efficiency for the i-th engineer respectively. Return the maximum performance of a team composed of at most k engineers, since the answer can be a huge number, return this modulo 10^9 + 7.

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

 

Example 1:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
Output: 60
Explanation: 
We have the maximum performance of the team by selecting engineer 2 (with speed=10 and efficiency=4) and engineer 5 (with speed=5 and efficiency=7). That is, performance = (10 + 5) * min(4, 7) = 60.

Example 2:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
Output: 68
Explanation:
This is the same example as the first but k = 3. We can select engineer 1, engineer 2 and engineer 5 to get the maximum performance of the team. That is, performance = (2 + 10 + 5) * min(5, 4, 7) = 68.

Example 3:

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

 

Constraints:

• 1 <= n <= 10^5
• speed.length == n
• efficiency.length == n
• 1 <= speed[i] <= 10^5
• 1 <= efficiency[i] <= 10^8
• 1 <= k <= n

Solution(javascript)

const MinHeap = () => {
  const list = []
  const parent = index => Math.floor((index - 1) / 2)
  const left = index => 2 * index + 1
  const right = index => 2 * index + 2

  const swap = (a, b) => {
    const temp = list[a]
    list[a] = list[b]
    list[b] = temp
  }
  const insert = (x) => {
    list.push(x)
    let currentIndex = list.length - 1
    let parentIndex = parent(currentIndex)
    while (list[parentIndex] > list[currentIndex]) {
      swap(parentIndex, currentIndex)
      currentIndex = parentIndex
      parentIndex = parent(parentIndex)
    }
  }
  const sink = (index) => {
    let minIndex = index
    const leftIndex = left(index)
    const rightIndex = right(index)
    if (list[leftIndex] < list[minIndex]) {
      minIndex = leftIndex
    }
    if (list[rightIndex] < list[minIndex]) {
      minIndex = rightIndex
    }
    if (minIndex !== index) {
      swap(minIndex, index)
      sink(minIndex)
    }
  }
  const size = () => list.length
  const extract = () => {
    swap(0, size() - 1)
    const min = list.pop()
    sink(0)
    return min
  }
  return {
    insert,
    size,
    extract,
  }
}

/** Heap Greedy
 * @param {number} n
 * @param {number[]} speed
 * @param {number[]} efficiency
 * @param {number} k
 * @return {number}
 */
const maxPerformance = function (n, speed, efficiency, k) {
  const works = speed.map((s, index) => [s, efficiency[index]])
  works.sort((a, b) => b[1] - a[1])
  let totalSpeed = 0
  let max = BigInt(0)
  const minHeap = MinHeap()
  for (const work of works) {
    if (minHeap.size() >= k) {
      const minSpeed = minHeap.extract()
      totalSpeed -= minSpeed
    }
    minHeap.insert(work[0])
    totalSpeed += work[0]
    const currentMax = BigInt(totalSpeed) * BigInt(work[1])
    if (currentMax > max) {
      max = currentMax
    }
  }
  const result = max % BigInt((10 ** 9) + 7)
  return Number(result)
}