Skip to content

Commit dbdc464

Browse files
halfrosthalfrost
committed
Add solution 1383
1 parent 640dc70 commit dbdc464

23 files changed

+735
-414
lines changed

‎README.md

Lines changed: 305 additions & 305 deletions
Large diffs are not rendered by default.

‎leetcode/1383.Maximum-Performance-of-a-Team/1383. Maximum Performance of a Team.go

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
package leetcode
2+
3+
import (
4+
"container/heap"
5+
"sort"
6+
)
7+
8+
func maxPerformance(n int, speed []int, efficiency []int, k int) int {
9+
indexes := make([]int, n)
10+
for i := range indexes {
11+
indexes[i] = i
12+
}
13+
sort.Slice(indexes, func(i, j int) bool {
14+
return efficiency[indexes[i]] > efficiency[indexes[j]]
15+
})
16+
ph := speedHeap{}
17+
heap.Init(&ph)
18+
speedSum := 0
19+
var max int64
20+
for _, index := range indexes {
21+
if ph.Len() == k {
22+
speedSum -= heap.Pop(&ph).(int)
23+
}
24+
speedSum += speed[index]
25+
heap.Push(&ph, speed[index])
26+
max = Max(max, int64(speedSum)*int64(efficiency[index]))
27+
}
28+
return int(max % (1e9 + 7))
29+
}
30+
31+
type speedHeap []int
32+
33+
func (h speedHeap) Less(i, j int) bool { return h[i] < h[j] }
34+
func (h speedHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
35+
func (h speedHeap) Len() int { return len(h) }
36+
func (h *speedHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
37+
func (h *speedHeap) Pop() interface{} {
38+
res := (*h)[len(*h)-1]
39+
*h = (*h)[:h.Len()-1]
40+
return res
41+
}
42+
43+
func Max(a, b int64) int64 {
44+
if a > b {
45+
return a
46+
}
47+
return b
48+
}

‎leetcode/1383.Maximum-Performance-of-a-Team/1383. Maximum Performance of a Team_test.go

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
package leetcode
2+
3+
import (
4+
"fmt"
5+
"testing"
6+
)
7+
8+
type question1383 struct {
9+
para1383
10+
ans1383
11+
}
12+
13+
// para 是参数
14+
// one 代表第一个参数
15+
type para1383 struct {
16+
n int
17+
speed []int
18+
efficiency []int
19+
k int
20+
}
21+
22+
// ans 是答案
23+
// one 代表第一个答案
24+
type ans1383 struct {
25+
one int
26+
}
27+
28+
func Test_Problem1383(t *testing.T) {
29+
30+
qs := []question1383{
31+
32+
{
33+
para1383{6, []int{2, 10, 3, 1, 5, 8}, []int{5, 4, 3, 9, 7, 2}, 2},
34+
ans1383{60},
35+
},
36+
37+
{
38+
para1383{6, []int{2, 10, 3, 1, 5, 8}, []int{5, 4, 3, 9, 7, 2}, 3},
39+
ans1383{68},
40+
},
41+
42+
{
43+
para1383{6, []int{2, 10, 3, 1, 5, 8}, []int{5, 4, 3, 9, 7, 2}, 4},
44+
ans1383{72},
45+
},
46+
}
47+
48+
fmt.Printf("------------------------Leetcode Problem 1383------------------------\n")
49+
50+
for _, q := range qs {
51+
_, p := q.ans1383, q.para1383
52+
fmt.Printf("【input】:%v 【output】:%v\n", p, maxPerformance(p.n, p.speed, p.efficiency, p.k))
53+
}
54+
fmt.Printf("\n\n\n")
55+
}

‎leetcode/1383.Maximum-Performance-of-a-Team/README.md

Lines changed: 105 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,105 @@
1+
# [1383. Maximum Performance of a Team](https://leetcode.com/problems/maximum-performance-of-a-team/)
2+
3+
## 题目
4+
5+
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.
6+
7+
Choose **at most** `k` different engineers out of the `n` engineers to form a team with the maximum **performance**.
8+
9+
The performance of a team is the sum of their engineers' speeds multiplied by the minimum efficiency among their engineers.
10+
11+
Return *the maximum performance of this team*. Since the answer can be a huge number, return it **modulo** `109 + 7`.
12+
13+
**Example 1:**
14+
15+
```
16+
Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
17+
Output: 60
18+
Explanation:
19+
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.
20+
```
21+
22+
**Example 2:**
23+
24+
```
25+
Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
26+
Output: 68
27+
Explanation:
28+
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.
29+
```
30+
31+
**Example 3:**
32+
33+
```
34+
Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
35+
Output: 72
36+
```
37+
38+
**Constraints:**
39+
40+
- `1 <= <= k <= n <= 105`
41+
- `speed.length == n`
42+
- `efficiency.length == n`
43+
- `1 <= speed[i] <= 105`
44+
- `1 <= efficiency[i] <= 108`
45+
46+
## 题目大意
47+
48+
公司有编号为 1 到 n 的 n 个工程师，给你两个数组 speed 和 efficiency ，其中 speed[i] 和 efficiency[i] 分别代表第 i 位工程师的速度和效率。请你返回由最多 k 个工程师组成的 最大团队表现值 ，由于答案可能很大，请你返回结果对 10^9 + 7 取余后的结果。团队表现值 的定义为：一个团队中「所有工程师速度的和」乘以他们「效率值中的最小值」。
49+
50+
## 解题思路
51+
52+
- 题目要求返回最大团队表现值，表现值需要考虑速度的累加和，和效率的最小值。即使速度快，效率的最小值很小，总的表现值还是很小。先将效率从大到小排序。从效率高的工程师开始选起，遍历过程中维护一个大小为 k 的速度最小堆。每次遍历都计算一次团队最大表现值。扫描完成，最大团队表现值也筛选出来了。具体实现见下面的代码。
53+
54+
## 代码
55+
56+
```go
57+
package leetcode
58+
59+
import (
60+
"container/heap"
61+
"sort"
62+
)
63+
64+
func maxPerformance(n int, speed []int, efficiency []int, k int) int {
65+
indexes := make([]int, n)
66+
for i := range indexes {
67+
indexes[i] = i
68+
}
69+
sort.Slice(indexes, func(i, j int) bool {
70+
return efficiency[indexes[i]] > efficiency[indexes[j]]
71+
})
72+
ph := speedHeap{}
73+
heap.Init(&ph)
74+
speedSum := 0
75+
var max int64
76+
for _, index := range indexes {
77+
if ph.Len() == k {
78+
speedSum -= heap.Pop(&ph).(int)
79+
}
80+
speedSum += speed[index]
81+
heap.Push(&ph, speed[index])
82+
max = Max(max, int64(speedSum)*int64(efficiency[index]))
83+
}
84+
return int(max % (1e9 + 7))
85+
}
86+
87+
type speedHeap []int
88+
89+
func (h speedHeap) Less(i, j int) bool { return h[i] < h[j] }
90+
func (h speedHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
91+
func (h speedHeap) Len() int { return len(h) }
92+
func (h *speedHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
93+
func (h *speedHeap) Pop() interface{} {
94+
res := (*h)[len(*h)-1]
95+
*h = (*h)[:h.Len()-1]
96+
return res
97+
}
98+
99+
func Max(a, b int64) int64 {
100+
if a > b {
101+
return a
102+
}
103+
return b
104+
}
105+
```

‎website/content/ChapterFour/1300~1399/1380.Lucky-Numbers-in-a-Matrix.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -90,5 +90,5 @@ func luckyNumbers(matrix [][]int) []int {
9090
----------------------------------------------
9191
<div style="display: flex;justify-content: space-between;align-items: center;">
9292
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/1300~1399/1353.Maximum-Number-of-Events-That-Can-Be-Attended/">⬅️上一页</a></p>
93-
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/1300~1399/1385.Find-the-Distance-Value-Between-Two-Arrays/">下一页➡️</a></p>
93+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/1300~1399/1383.Maximum-Performance-of-a-Team/">下一页➡️</a></p>
9494
</div>

‎website/content/ChapterFour/1300~1399/1383.Maximum-Performance-of-a-Team.md

Lines changed: 112 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,112 @@
1+
# [1383. Maximum Performance of a Team](https://leetcode.com/problems/maximum-performance-of-a-team/)
2+
3+
## 题目
4+
5+
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.
6+
7+
Choose **at most** `k` different engineers out of the `n` engineers to form a team with the maximum **performance**.
8+
9+
The performance of a team is the sum of their engineers' speeds multiplied by the minimum efficiency among their engineers.
10+
11+
Return *the maximum performance of this team*. Since the answer can be a huge number, return it **modulo** `109 + 7`.
12+
13+
**Example 1:**
14+
15+
```
16+
Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
17+
Output: 60
18+
Explanation:
19+
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.
20+
```
21+
22+
**Example 2:**
23+
24+
```
25+
Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
26+
Output: 68
27+
Explanation:
28+
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.
29+
```
30+
31+
**Example 3:**
32+
33+
```
34+
Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
35+
Output: 72
36+
```
37+
38+
**Constraints:**
39+
40+
- `1 <= <= k <= n <= 105`
41+
- `speed.length == n`
42+
- `efficiency.length == n`
43+
- `1 <= speed[i] <= 105`
44+
- `1 <= efficiency[i] <= 108`
45+
46+
## 题目大意
47+
48+
公司有编号为 1 到 n 的 n 个工程师，给你两个数组 speed 和 efficiency ，其中 speed[i] 和 efficiency[i] 分别代表第 i 位工程师的速度和效率。请你返回由最多 k 个工程师组成的 最大团队表现值 ，由于答案可能很大，请你返回结果对 10^9 + 7 取余后的结果。团队表现值 的定义为：一个团队中「所有工程师速度的和」乘以他们「效率值中的最小值」。
49+
50+
## 解题思路
51+
52+
- 题目要求返回最大团队表现值，表现值需要考虑速度的累加和，和效率的最小值。即使速度快，效率的最小值很小，总的表现值还是很小。先将效率从大到小排序。从效率高的工程师开始选起，遍历过程中维护一个大小为 k 的速度最小堆。每次遍历都计算一次团队最大表现值。扫描完成，最大团队表现值也筛选出来了。具体实现见下面的代码。
53+
54+
## 代码
55+
56+
```go
57+
package leetcode
58+
59+
import (
60+
"container/heap"
61+
"sort"
62+
)
63+
64+
func maxPerformance(n int, speed []int, efficiency []int, k int) int {
65+
indexes := make([]int, n)
66+
for i := range indexes {
67+
indexes[i] = i
68+
}
69+
sort.Slice(indexes, func(i, j int) bool {
70+
return efficiency[indexes[i]] > efficiency[indexes[j]]
71+
})
72+
ph := speedHeap{}
73+
heap.Init(&ph)
74+
speedSum := 0
75+
var max int64
76+
for _, index := range indexes {
77+
if ph.Len() == k {
78+
speedSum -= heap.Pop(&ph).(int)
79+
}
80+
speedSum += speed[index]
81+
heap.Push(&ph, speed[index])
82+
max = Max(max, int64(speedSum)*int64(efficiency[index]))
83+
}
84+
return int(max % (1e9 + 7))
85+
}
86+
87+
type speedHeap []int
88+
89+
func (h speedHeap) Less(i, j int) bool { return h[i] < h[j] }
90+
func (h speedHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
91+
func (h speedHeap) Len() int { return len(h) }
92+
func (h *speedHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
93+
func (h *speedHeap) Pop() interface{} {
94+
res := (*h)[len(*h)-1]
95+
*h = (*h)[:h.Len()-1]
96+
return res
97+
}
98+
99+
func Max(a, b int64) int64 {
100+
if a > b {
101+
return a
102+
}
103+
return b
104+
}
105+
```
106+
107+
108+
----------------------------------------------
109+
<div style="display: flex;justify-content: space-between;align-items: center;">
110+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/1300~1399/1380.Lucky-Numbers-in-a-Matrix/">⬅️上一页</a></p>
111+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/1300~1399/1385.Find-the-Distance-Value-Between-Two-Arrays/">下一页➡️</a></p>
112+
</div>

‎website/content/ChapterFour/1300~1399/1385.Find-the-Distance-Value-Between-Two-Arrays.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -100,6 +100,6 @@ func abs(a int) int {
100100

101101
----------------------------------------------
102102
<div style="display: flex;justify-content: space-between;align-items: center;">
103-
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/1300~1399/1380.Lucky-Numbers-in-a-Matrix/">⬅️上一页</a></p>
103+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/1300~1399/1383.Maximum-Performance-of-a-Team/">⬅️上一页</a></p>
104104
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/1300~1399/1389.Create-Target-Array-in-the-Given-Order/">下一页➡️</a></p>
105105
</div>

0 commit comments

Comments
 (0)