8000 add 826 · githubniraj/Leetcode@3574718 · GitHub
[go: up one dir, main page]
Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 3574718

Browse files
fishercoder1534fishercoder1534
committed
add 826
1 parent b4c9582 commit 3574718

File tree

3 files changed

+79
-0
lines changed
  • paginated_contents/algorithms/1st_thousand
  • src
    • main/java/com/fishercoder/solutions/firstthousand
    • test/java/com/fishercoder/firstthousand

3 files changed

+79
-0
lines changed

‎paginated_contents/algorithms/1st_thousand/README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -86,6 +86,7 @@
8686
| 836 | [Rectangle Overlap](https://leetcode.com/problems/rectangle-overlap/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_836.java) | [:tv:](https://youtu.be/o6hHUk4DOW0) | Easy |
8787
| 832 | [Flipping an Image](https://leetcode.com/problems/flipping-an-image/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_832.java) | | Easy |
8888
| 830 | [Positions of Large Groups](https://leetcode.com/problems/positions-of-large-groups/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_830.java) | | Easy |
89+
| 826 | [Most Profit Assigning Work](https://leetcode.com/problems/most-profit-assigning-work/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_826.java) | | Medium |Binary Search, Greedy, Sorting
8990
| 824 | [Goat Latin](https://leetcode.com/problems/goat-latin/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_824.java) | | Easy |
9091
| 823 | [Binary Trees With Factors](https://leetcode.com/problems/binary-trees-with-factors/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_823.java) | | Medium |
9192
| 821 | [Shortest Distance to a Character](https://leetcode.com/problems/shortest-distance-to-a-character/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_821.java) | | Easy |

‎src/main/java/com/fishercoder/solutions/firstthousand/_826.java

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
package com.fishercoder.solutions.firstthousand;
2+
3+
import java.util.ArrayList;
4+
import java.util.Collections;
5+
import java.util.List;
6+
7+
public class _826 {
8+
public static class Solution1 {
9+
public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
10+
List<int[]> jobs = new ArrayList<>();
11+
for (int i = 0; i < difficulty.length; i++) {
12+
jobs.add(new int[]{difficulty[i], profit[i]});
13+
}
14+
//sort by difficulty level
15+
Collections.sort(jobs, (a, b) -> a[0] - b[0]);
16+
17+
//update the profit values: because a later (with more difficult) job must be able to handle a prior job, so we take the more profitable one
18+
for (int i = 0; i < jobs.size() - 1; i++) {
19+
jobs.get(i + 1)[1] = Math.max(jobs.get(i)[1], jobs.get(i + 1)[1]);
20+
}
21+
22+
int maxProfit = 0;
23+
for (int ability : worker) {
24+
maxProfit += binarySearch(ability, jobs);
25+
}
26+
return maxProfit;
27+
}
28+
29+
private int binarySearch(int ability, List<int[]> jobs) {
30+
int left = 0;
31+
int right = jobs.size() - 1;
32+
int maxProfit = 0;
33+
//it's important to use <= here so we don't miss a possible element
34+
while (left <= right) {
35+
int mid = left + (right - left) / 2;
36+
if (ability >= jobs.get(mid)[0]) {
37+
maxProfit = Math.max(jobs.get(mid)[1], maxProfit);
38+
left = mid + 1;
39+
} else {
40+
right = mid - 1;
41+
}
42+
}
43+
return maxProfit;
44+
}
45+
46+
}
47+
}

‎src/test/java/com/fishercoder/firstthousand/_826Test.java

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
package com.fishercoder.firstthousand;
2+
3+
import com.fishercoder.solutions.firstthousand._826;
4+
import org.junit.jupiter.api.BeforeEach;
5+
import org.junit.jupiter.api.Test;
6+
7+
import static org.junit.jupiter.api.Assertions.assertEquals;
8+
9+
public class _826Test {
10+
private static _826.Solution1 solution1;
11+
12+
@BeforeEach
13+
public void setup() {
14+
solution1 = new _826.Solution1();
15+
}
16+
17+
@Test
18+
public void test1() {
19+
assertEquals(100, solution1.maxProfitAssignment(new int[]{2, 4, 6, 8, 10}, new int[]{10, 20, 30, 40, 50}, new int[]{4, 5, 6, 7}));
20+
}
21+
22+
@Test
23+
public void test2() {
24+
assertEquals(324, solution1.maxProfitAssignment(new int[]{68, 35, 52, 47, 86}, new int[]{67, 17, 1, 81, 3}, new int[]{92, 10, 85, 84, 82}));
25+
}
26+
27+
@Test
28+
public void test3() {
29+
assertEquals(190, solution1.maxProfitAssignment(new int[]{13, 37, 58}, new int[]{4, 90, 96}, new int[]{34, 73, 45}));
30+
}
31+
}

0 commit comments

Comments
 (0)
0