package leetcode;

import java.util.Arrays;
import java.util.Comparator;

/**
 * https://leetcode.com/problems/most-profit-assigning-work/
 */
public class Problem826 {
    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        // TODO
        DifficultyProfit[] dp = new DifficultyProfit[difficulty.length];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = new DifficultyProfit(difficulty[i], profit[i]);
        }
        Arrays.sort(dp, Comparator.comparingInt(a -> a.difficulty));
        int maxProfit = 0;
        for (int i = 0; i < dp.length; i++) {
            maxProfit = Math.max(maxProfit, dp[i].profit);
            dp[i].profit = maxProfit;
        }
        return 0;
    }

    private static class DifficultyProfit {
        private final int difficulty;
        private int profit;

        public DifficultyProfit(int difficulty, int profit) {
            this.difficulty = difficulty;
            this.profit = profit;
        }

        @Override
        public String toString() {
            return difficulty + " -> " + profit;
        }
    }

    public static void main(String[] args) {
        Problem826 prob = new Problem826();
        System.out.println(prob.maxProfitAssignment(new int[]{2, 4, 6, 8, 10},
            new int[]{10, 20, 30, 40, 50}, new int[]{4, 5, 6, 7})); // 100
        System.out.println(prob.maxProfitAssignment(new int[]{2, 4, 6, 8, 10},
            new int[]{10, 5, 30, 40, 50}, new int[]{4, 5, 6, 7})); // 80
    }
}

@@ -249,24 +249,8 @@
 ) %7B%0A
-        // TODO%0A
     
@@ -703,16 +703,480 @@
     
-return 0
+int result = 0;%0A        for (int i = 0; i %3C worker.length; i++) %7B%0A            int idx = Arrays.binarySearch(dp, new DifficultyProfit(worker%5Bi%5D, 0),%0A                Comparator.comparingInt(a -%3E a.difficulty));%0A            if (idx %3C 0) %7B%0A                idx = -idx - 2;%0A                if (idx %3E= 0) %7B%0A                    result += dp%5Bidx%5D.profit;%0A                %7D%0A            %7D else %7B%0A                result += dp%5Bidx%5D.profit;%0A            %7D%0A        %7D%0A        return result
 ;%0A  
@@ -1648,16 +1648,18 @@
 m826();%0A
+//
         
@@ -1694,32 +1694,47 @@
 rofitAssignment(
+%0A//            
 new int%5B%5D%7B2, 4, 
@@ -1736,32 +1736,34 @@
 , 4, 6, 8, 10%7D,%0A
+//
             new 
@@ -1780,32 +1780,46 @@
 20, 30, 40, 50%7D,
+%0A//           
  new int%5B%5D%7B4, 5,
@@ -1887,16 +1887,212 @@
 ignment(
+%0A            new int%5B%5D%7B4, 4, 6, 8, 10%7D,%0A            new int%5B%5D%7B10, 30, 30, 40, 50%7D,%0A            new int%5B%5D%7B4, 5, 6, 7%7D)); // 120%0A//        System.out.println(prob.maxProfitAssignment(%0A//            
 new int%5B
@@ -2102,32 +2102,34 @@
 , 4, 6, 8, 10%7D,%0A
+//
             new 
@@ -2153,16 +2153,30 @@
 40, 50%7D,
+%0A//           
  new int
@@ -2199,16 +2199,274 @@
 ; // 80%0A
+//        System.out.println(prob.maxProfitAssignment(%0A//            new int%5B%5D%7B23, 30, 35, 35, 43, 46, 47, 81, 83, 98%7D,%0A//            new int%5B%5D%7B8, 11, 11, 20, 33, 37, 60, 72, 87, 95%7D,%0A//            new int%5B%5D%7B95, 46, 47, 97, 11, 35, 99, 56, 41, 92%7D)); // 553%0A
     %7D%0A%7D%0A

Update problem 826