FilesExpand file tree

 master

/

MostProfitAssigningWork826.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

59 lines (56 loc) · 1.8 KB

 master

/

MostProfitAssigningWork826.java

Copy path

Top

File metadata and controls

• Code
• Blame

59 lines (56 loc) · 1.8 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

/**

* We have jobs: difficulty[i] is the difficulty of the ith job, and profit[i]

* is the profit of the ith job.

*

* Now we have some workers. worker[i] is the ability of the ith worker, which

* means that this worker can only complete a job with difficulty at most

* worker[i].

*

* Every worker can be assigned at most one job, but one job can be completed

* multiple times.

*

* For example, if 3 people attempt the same job that pays $1, then the total

* profit will be $3. If a worker cannot complete any job, his profit is $0.

*

* What is the most profit we can make?

*

* Example 1:

*

* Input: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]

* Output: 100

* Explanation: Workers are assigned jobs of difficulty [4,4,6,6] and they get

* profit of [20,20,30,30] seperately.

*

* Notes:

* 1 <= difficulty.length = profit.length <= 10000

* 1 <= worker.length <= 10000

* difficulty[i], profit[i], worker[i] are in range [1, 10^5]

*/

public class MostProfitAssigningWork826 {

public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {

int N = difficulty.length;

Job[] jobs = new Job[N];

for (int i=0; i<N; i++) jobs[i] = new Job(difficulty[i], profit[i]);

Arrays.sort(jobs, (j1, j2) -> Integer.compare(j1.difficulty, j2.difficulty));

Arrays.sort(worker);

int res = 0;

int max = 0;

int i = 0;

for (int cap: worker) {

while (i < N && jobs[i].difficulty <= cap) {

max = Math.max(max, jobs[i].profit);

i++;

}

res += max;

}

return res;

}

class Job {

int difficulty;

int profit;

Job (int d, int p) {

difficulty = d;

profit = p;

}

}

}