1383. Maximum Performance of a Team #

Problem #

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 their engineers’ speeds multiplied by the minimum efficiency among their engineers.

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

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 <= <= k <= n <= 105
• speed.length == n
• efficiency.length == n
• 1 <= speed[i] <= 105
• 1 <= efficiency[i] <= 108

Problem Summary #

There are n engineers in a company, numbered from 1 to n. You are given two arrays, speed and efficiency, where speed[i] and efficiency[i] represent the speed and efficiency of the ith engineer respectively. Return the maximum team performance value of a team consisting of at most k engineers. Since the answer may be very large, return the result modulo 10^9 + 7. The team performance value is defined as: the sum of the speeds of all engineers in a team multiplied by the minimum efficiency value among them.

Solution Approach #

• The problem asks us to return the maximum team performance value, which needs to consider both the accumulated sum of speeds and the minimum efficiency. Even if the speed is high, if the minimum efficiency is very small, the overall performance value will still be very small. First sort the engineers by efficiency in descending order. Starting from the engineer with the highest efficiency, maintain a min-heap of speeds with size k during the traversal. Compute the maximum team performance value at each traversal step. After the scan is complete, the maximum team performance value has also been determined. See the code below for the specific implementation.

Code #

package leetcode

import (
	"container/heap"
	"sort"
)

func maxPerformance(n int, speed []int, efficiency []int, k int) int {
	indexes := make([]int, n)
	for i := range indexes {
		indexes[i] = i
	}
	sort.Slice(indexes, func(i, j int) bool {
		return efficiency[indexes[i]] > efficiency[indexes[j]]
	})
	ph := speedHeap{}
	heap.Init(&ph)
	speedSum := 0
	var max int64
	for _, index := range indexes {
		if ph.Len() == k {
			speedSum -= heap.Pop(&ph).(int)
		}
		speedSum += speed[index]
		heap.Push(&ph, speed[index])
		max = Max(max, int64(speedSum)*int64(efficiency[index]))
	}
	return int(max % (1e9 + 7))
}

type speedHeap []int

func (h speedHeap) Less(i, j int) bool  { return h[i] < h[j] }
func (h speedHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h speedHeap) Len() int            { return len(h) }
func (h *speedHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *speedHeap) Pop() interface{} {
	res := (*h)[len(*h)-1]
	*h = (*h)[:h.Len()-1]
	return res
}

func Max(a, b int64) int64 {
	if a > b {
		return a
	}
	return b
}