Skip to content

Commit e2ceae8

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.1383
No.1383.Maximum Performance of a Team
1 parent 572c550 commit e2ceae8

File tree

8 files changed

+230
-107
lines changed

8 files changed

+230
-107
lines changed

‎solution/0800-0899/0857.Minimum Cost to Hire K Workers/README.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -60,6 +60,8 @@
6060

6161
时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。其中 $n$ 是工人数。
6262

63+
相似题目：[1383. 最大的团队表现值](/solution/1300-1399/1383.Maximum%20Performance%20of%20a%20Team/README.md)
64+
6365
<!-- tabs:start -->
6466

6567
### **Python3**

‎solution/1300-1399/1382.Balance a Binary Search Tree/README.md

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -103,7 +103,6 @@ class Solution:
103103
* }
104104
*/
105105
class Solution {
106-
107106
private List<Integer> vals;
108107

109108
public TreeNode balanceBST(TreeNode root) {

‎solution/1300-1399/1383.Maximum Performance of a Team/README.md

Lines changed: 82 additions & 37 deletions
Original file line numberDiff line numberDiff line change
@@ -51,9 +51,13 @@
5151

5252
<!-- 这里可写通用的实现逻辑 -->
5353

54-
**方法一：优先队列**
54+
**方法一：贪心 + 优先队列（小根堆）**
5555

56-
本题是求“速度和”与“效率最小值”乘积的最大值。变量有两个，我们可以从大到小枚举 `efficiency[i]` 作为效率最小值，在所有效率大于等于 `efficiency[i]` 的工程师中选取不超过 k-1 个，让他们速度和最大。
56+
本题是求“速度和”与“效率最小值”乘积的最大值。变量有两个，我们可以从大到小枚举 `efficiency[i]` 作为效率最小值，在所有效率大于等于 `efficiency[i]` 的工程师中选取不超过 $k-1$ 个，让他们速度和最大。
57+
58+
时间复杂度 $O(n\log n)$。
59+
60+
相似题目：[857. 雇佣 K 名工人的最低成本](/solution/0800-0899/0857.Minimum%20Cost%20to%20Hire%20K%20Workers/README.md)
5761

5862
<!-- tabs:start -->
5963

@@ -66,18 +70,16 @@ class Solution:
6670
def maxPerformance(
6771
self, n: int, speed: List[int], efficiency: List[int], k: int
6872
) -> int:
69-
team = [(s, e) for s, e in zip(speed, efficiency)]
70-
team.sort(key=lambda x: -x[1])
71-
q = []
72-
t = 0
73-
ans = 0
74-
mod = int(1e9) + 7
75-
for s, e in team:
76-
t += s
77-
ans = max(ans, t * e)
78-
heappush(q, s)
79-
if len(q) >= k:
80-
t -= heappop(q)
73+
t = sorted(zip(speed, efficiency), key=lambda x: -x[1])
74+
ans = tot = 0
75+
mod = 10**9 + 7
76+
h = []
77+
for s, e in t:
78+
tot += s
79+
ans = max(ans, tot * e)
80+
heappush(h, s)
81+
if len(h) == k:
82+
tot -= heappop(h)
8183
return ans % mod
8284
```
8385

@@ -87,26 +89,27 @@ class Solution:
8789

8890
```java
8991
class Solution {
92+
private static final int MOD = (int) 1e9 + 7;
93+
9094
public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
91-
int[][] team = new int[n][2];
95+
int[][] t = new int[n][2];
9296
for (int i = 0; i < n; ++i) {
93-
team[i] = new int[] {speed[i], efficiency[i]};
97+
t[i] = new int[] {speed[i], efficiency[i]};
9498
}
95-
Arrays.sort(team, (a, b) -> b[1] - a[1]);
96-
PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> a - b);
97-
long t = 0;
99+
Arrays.sort(t, (a, b) -> b[1] - a[1]);
100+
PriorityQueue<Integer> q = new PriorityQueue<>();
101+
long tot = 0;
98102
long ans = 0;
99-
int mod = (int) 1e9 + 7;
100-
for (int[] x : team) {
103+
for (var x : t) {
101104
int s = x[0], e = x[1];
102-
t += s;
103-
ans = Math.max(ans, t * e);
105+
tot += s;
106+
ans = Math.max(ans, tot * e);
104107
q.offer(s);
105-
if (q.size() >= k) {
106-
t -= q.poll();
108+
if (q.size() == k) {
109+
tot -= q.poll();
107110
}
108111
}
109-
return (int) (ans % mod);
112+
return (int) (ans % MOD);
110113
}
111114
}
112115
```
@@ -117,28 +120,70 @@ class Solution {
117120
class Solution {
118121
public:
119122
int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
120-
vector<pair<int, int>> team;
121-
for (int i = 0; i < n; ++i) team.push_back({-efficiency[i], speed[i]});
122-
sort(team.begin(), team.end());
123+
vector<pair<int, int>> t(n);
124+
for (int i = 0; i < n; ++i) t[i] = {-efficiency[i], speed[i]};
125+
sort(t.begin(), t.end());
123126
priority_queue<int, vector<int>, greater<int>> q;
124-
long long ans = 0;
127+
long long ans = 0, tot = 0;
125128
int mod = 1e9 + 7;
126-
long long t = 0;
127-
for (auto& x : team) {
129+
for (auto& x : t) {
128130
int s = x.second, e = -x.first;
129-
t += s;
130-
ans = max(ans, e * t);
131+
tot += s;
132+
ans = max(ans, tot * e);
131133
q.push(s);
132-
if (q.size() >= k) {
133-
t -= q.top();
134+
if (q.size() == k) {
135+
tot -= q.top();
134136
q.pop();
135137
}
136138
}
137-
return (int)(ans % mod);
139+
return (int) (ans % mod);
138140
}
139141
};
140142
```
141143
144+
### **Go**
145+
146+
```go
147+
func maxPerformance(n int, speed []int, efficiency []int, k int) int {
148+
t := make([][]int, n)
149+
for i, s := range speed {
150+
t[i] = []int{s, efficiency[i]}
151+
}
152+
sort.Slice(t, func(i, j int) bool { return t[i][1] > t[j][1] })
153+
var mod int = 1e9 + 7
154+
ans, tot := 0, 0
155+
pq := hp{}
156+
for _, x := range t {
157+
s, e := x[0], x[1]
158+
tot += s
159+
ans = max(ans, tot*e)
160+
heap.Push(&pq, s)
161+
if pq.Len() == k {
162+
tot -= heap.Pop(&pq).(int)
163+
}
164+
}
165+
return ans % mod
166+
}
167+
168+
func max(a, b int) int {
169+
if a > b {
170+
return a
171+
}
172+
return b
173+
}
174+
175+
type hp struct{ sort.IntSlice }
176+
177+
func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
178+
func (h *hp) Pop() interface{} {
179+
a := h.IntSlice
180+
v := a[len(a)-1]
181+
h.IntSlice = a[:len(a)-1]
182+
return v
183+
}
184+
func (h *hp) Less(i, j int) bool { return h.IntSlice[i] < h.IntSlice[j] }
185+
```
186+
142187
### **...**
143188

144189
```

‎solution/1300-1399/1383.Maximum Performance of a Team/README_EN.md

Lines changed: 76 additions & 35 deletions
Original file line numberDiff line numberDiff line change
@@ -60,45 +60,44 @@ class Solution:
6060
def maxPerformance(
6161
self, n: int, speed: List[int], efficiency: List[int], k: int
6262
) -> int:
63-
team = [(s, e) for s, e in zip(speed, efficiency)]
64-
team.sort(key=lambda x: -x[1])
65-
q = []
66-
t = 0
67-
ans = 0
68-
mod = int(1e9) + 7
69-
for s, e in team:
70-
t += s
71-
ans = max(ans, t * e)
72-
heappush(q, s)
73-
if len(q) >= k:
74-
t -= heappop(q)
63+
t = sorted(zip(speed, efficiency), key=lambda x: -x[1])
64+
ans = tot = 0
65+
mod = 10**9 + 7
66+
h = []
67+
for s, e in t:
68+
tot += s
69+
ans = max(ans, tot * e)
70+
heappush(h, s)
71+
if len(h) == k:
72+
tot -= heappop(h)
7573
return ans % mod
7674
```
7775

7876
### **Java**
7977

8078
```java
8179
class Solution {
80+
private static final int MOD = (int) 1e9 + 7;
81+
8282
public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
83-
int[][] team = new int[n][2];
83+
int[][] t = new int[n][2];
8484
for (int i = 0; i < n; ++i) {
85-
team[i] = new int[] {speed[i], efficiency[i]};
85+
t[i] = new int[] {speed[i], efficiency[i]};
8686
}
87-
Arrays.sort(team, (a, b) -> b[1] - a[1]);
88-
PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> a - b);
89-
long t = 0;
87+
Arrays.sort(t, (a, b) -> b[1] - a[1]);
88+
PriorityQueue<Integer> q = new PriorityQueue<>();
89+
long tot = 0;
9090
long ans = 0;
91-
int mod = (int) 1e9 + 7;
92-
for (int[] x : team) {
91+
for (var x : t) {
9392
int s = x[0], e = x[1];
94-
t += s;
95-
ans = Math.max(ans, t * e);
93+
tot += s;
94+
ans = Math.max(ans, tot * e);
9695
q.offer(s);
97-
if (q.size() >= k) {
98-
t -= q.poll();
96+
if (q.size() == k) {
97+
tot -= q.poll();
9998
}
10099
}
101-
return (int) (ans % mod);
100+
return (int) (ans % MOD);
102101
}
103102
}
104103
```
@@ -109,28 +108,70 @@ class Solution {
109108
class Solution {
110109
public:
111110
int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
112-
vector<pair<int, int>> team;
113-
for (int i = 0; i < n; ++i) team.push_back({-efficiency[i], speed[i]});
114-
sort(team.begin(), team.end());
111+
vector<pair<int, int>> t(n);
112+
for (int i = 0; i < n; ++i) t[i] = {-efficiency[i], speed[i]};
113+
sort(t.begin(), t.end());
115114
priority_queue<int, vector<int>, greater<int>> q;
116-
long long ans = 0;
115+
long long ans = 0, tot = 0;
117116
int mod = 1e9 + 7;
118-
long long t = 0;
119-
for (auto& x : team) {
117+
for (auto& x : t) {
120118
int s = x.second, e = -x.first;
121-
t += s;
122-
ans = max(ans, e * t);
119+
tot += s;
120+
ans = max(ans, tot * e);
123121
q.push(s);
124-
if (q.size() >= k) {
125-
t -= q.top();
122+
if (q.size() == k) {
123+
tot -= q.top();
126124
q.pop();
127125
}
128126
}
129-
return (int)(ans % mod);
127+
return (int) (ans % mod);
130128
}
131129
};
132130
```
133131
132+
### **Go**
133+
134+
```go
135+
func maxPerformance(n int, speed []int, efficiency []int, k int) int {
136+
t := make([][]int, n)
137+
for i, s := range speed {
138+
t[i] = []int{s, efficiency[i]}
139+
}
140+
sort.Slice(t, func(i, j int) bool { return t[i][1] > t[j][1] })
141+
var mod int = 1e9 + 7
142+
ans, tot := 0, 0
143+
pq := hp{}
144+
for _, x := range t {
145+
s, e := x[0], x[1]
146+
tot += s
147+
ans = max(ans, tot*e)
148+
heap.Push(&pq, s)
149+
if pq.Len() == k {
150+
tot -= heap.Pop(&pq).(int)
151+
}
152+
}
153+
return ans % mod
154+
}
155+
156+
func max(a, b int) int {
157+
if a > b {
158+
return a
159+
}
160+
return b
161+
}
162+
163+
type hp struct{ sort.IntSlice }
164+
165+
func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
166+
func (h *hp) Pop() interface{} {
167+
a := h.IntSlice
168+
v := a[len(a)-1]
169+
h.IntSlice = a[:len(a)-1]
170+
return v
171+
}
172+
func (h *hp) Less(i, j int) bool { return h.IntSlice[i] < h.IntSlice[j] }
173+
```
174+
134175
### **...**
135176

136177
```

‎solution/1300-1399/1383.Maximum Performance of a Team/Solution.cpp

Lines changed: 9 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,20 +1,19 @@
11
class Solution {
22
public:
33
int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
4-
vector<pair<int, int>> team;
5-
for (int i = 0; i < n; ++i) team.push_back({-efficiency[i], speed[i]});
6-
sort(team.begin(), team.end());
4+
vector<pair<int, int>> t(n);
5+
for (int i = 0; i < n; ++i) t[i] = {-efficiency[i], speed[i]};
6+
sort(t.begin(), t.end());
77
priority_queue<int, vector<int>, greater<int>> q;
8-
long long ans = 0;
8+
long long ans = 0, tot = 0;
99
int mod = 1e9 + 7;
10-
long long t = 0;
11-
for (auto& x : team) {
10+
for (auto& x : t) {
1211
int s = x.second, e = -x.first;
13-
t += s;
14-
ans = max(ans, e * t);
12+
tot += s;
13+
ans = max(ans, tot * e);
1514
q.push(s);
16-
if (q.size() >= k) {
17-
t -= q.top();
15+
if (q.size() == k) {
16+
tot -= q.top();
1817
q.pop();
1918
}
2019
}

0 commit comments

Comments
 (0)