826. Most Profit Assigning Work

Version #3 Greedy

56.20 %
class Solution {
    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        Arrays.sort(worker);
        int len = difficulty.length;
        int[][] tuple = new int[len][2];
        // worker[i + 1] can always finish work that worker[i] is assigned
        for (int i = 0; i < len; i++) {
            tuple[i][0] = difficulty[i];
            tuple[i][1] = profit[i];
        }
        Arrays.sort(tuple, Comparator.comparing(a -> a[0]));
        int curr = -1;
        int bestIndex = -1;
        int result = 0;
        for (int i = 0; i < worker.length; i++) {
            // check if this worker can do a more difficult work
            while (curr + 1 < len && tuple[curr + 1][0] <= worker[i]) {
                curr++;
                if (bestIndex == -1 || tuple[curr][1] > tuple[bestIndex][1]) bestIndex = curr;
            }
            result += bestIndex == -1 ? 0 : tuple[bestIndex][1];
        }
        return result;
    }
}




Version #2 Sort both Tuple and Worker + Two Pointers
A worker can always finish the work that one has less difficulty can do

63.82 %
class Solution {
    class Tuple {
int dif;
int prof;
public Tuple(int dif, int prof) {
this.dif = dif;
this.prof = prof;
}
}
public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
List<Tuple> list = new ArrayList<>();
for (int i = 0; i < difficulty.length; i++) {
list.add(new Tuple(difficulty[i], profit[i]));
}
// difficulty in ascending order, profit in descending order
Collections.sort(list, (t1, t2) -> {
if (t1.dif == t2.dif) {
return t2.prof - t1.prof;
} else {
return t1.dif - t2.dif;
}
});
int maxProf = 0;
int result = 0;
Arrays.sort(worker);
int i = 0;
int j = 0;
while (i < worker.length) {
while (j < list.size() && list.get(j).dif <= worker[i]) {
maxProf = Math.max(maxProf, list.get(j).prof);
j++;
}
result += maxProf;
i++;
}
return result;
}
}


Version #1 Sort + BinarySearch
Self defined class with sort Tuple
Time O(mnlogn)
32.48 %

class Solution {
    class Tuple {
int dif;
int prof;
public Tuple(int dif, int prof) {
this.dif = dif;
this.prof = prof;
}
}
public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
List<Tuple> list = new ArrayList<>();
for (int i = 0; i < difficulty.length; i++) {
list.add(new Tuple(difficulty[i], profit[i]));
}
// difficulty in descending order, profit in descending order
Collections.sort(list, (t1, t2) -> {
if (t1.dif == t2.dif) {
return t2.prof - t1.prof;
} else {
return t2.dif - t1.dif;
}
});
int maxProf = 0;
for (int i = list.size() - 1; i >= 0; i--) {
Tuple curr = list.get(i);
maxProf = Math.max(maxProf, list.get(i).prof);
curr.prof = maxProf;
}
int result = 0;
// Find the profit first tuple whose difficulty is smaller than current
for (int w : worker) {
result += binarySearch(list, w);
}
return result;
}

private int binarySearch(List<Tuple> list, int target) {
int start = 0;
int end = list.size() - 1;
while (start < end) {
int mid = start + (end - start) / 2;
if (list.get(mid).dif > target) {
start = mid + 1;
} else {
end = mid;
}
}
return list.get(start).dif <= target ? list.get(start).prof : 0;
}
}