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) {
        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;
        }
        int result = 0;
        for (int i = 0; i < worker.length; i++) {
            int idx = Arrays.binarySearch(dp, new DifficultyProfit(worker[i], 0),
                Comparator.comparingInt(a -> a.difficulty));
            if (idx < 0) {
                idx = -idx - 2;
                if (idx >= 0) {
                    result += dp[idx].profit;
                }
            } else {
                result += dp[idx].profit;
            }
        }
        return result;
    }

    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[]{4, 4, 6, 8, 10},
            new int[]{10, 30, 30, 40, 50},
            new int[]{4, 5, 6, 7})); // 120
//        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
//        System.out.println(prob.maxProfitAssignment(
//            new int[]{23, 30, 35, 35, 43, 46, 47, 81, 83, 98},
//            new int[]{8, 11, 11, 20, 33, 37, 60, 72, 87, 95},
//            new int[]{95, 46, 47, 97, 11, 35, 99, 56, 41, 92})); // 553
    }
}

@@ -34,42 +34,195 @@
 il.A
-rrays;%0Aimport java.util.Comparator
+bstractMap.SimpleImmutableEntry;%0Aimport java.util.Arrays;%0Aimport java.util.Comparator;%0Aimport java.util.HashMap;%0Aimport java.util.Map;%0Aimport java.util.Map.Entry;%0Aimport java.util.TreeSet
 ;%0A%0A/
@@ -656,32 +656,85 @@
 a.difficulty));%0A
+        Map%3CInteger, Integer%3E map = new HashMap%3C%3E();%0A
         int maxP
@@ -865,22 +865,33 @@
     
-dp%5Bi%5D.profit =
+map.put(dp%5Bi%5D.difficulty,
  max
@@ -892,24 +892,25 @@
 y, maxProfit
+)
 ;%0A        %7D%0A
@@ -945,135 +945,62 @@
     
-for (int i = 0; i %3C worker.length; i++) %7B%0A            int idx = Arrays.binarySearch(dp, new DifficultyProfit(worker%5Bi%5D, 0),%0A   
+TreeSet%3CEntry%3CInteger, Integer%3E%3E set = new TreeSet%3C%3E(%0A
     
@@ -1007,17 +1007,16 @@
         
- 
 Comparat
@@ -1035,202 +1035,238 @@
 Int(
-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
+Entry::getKey));%0A        set.addAll(map.entrySet());%0A        for (int i = 0; i %3C worker.length; i++) %7B%0A            Entry%3CInteger, Integer%3E entry = set.floor(new SimpleImmutableEntry%3C%3E(worker%5Bi%5D, 0));%0A            if (entry != null)
  %7B%0A 
@@ -1294,22 +1294,24 @@
  += 
-dp%5Bidx%5D.profit
+entry.getValue()
 ;%0A  
@@ -1624,1026 +1624,8 @@
    %7D
-%0A%0A        @Override%0A        public String toString() %7B%0A            return difficulty + %22 -%3E %22 + profit;%0A        %7D%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem826 prob = new Problem826();%0A//        System.out.println(prob.maxProfitAssignment(%0A//            new int%5B%5D%7B2, 4, 6, 8, 10%7D,%0A//            new int%5B%5D%7B10, 20, 30, 40, 50%7D,%0A//            new int%5B%5D%7B4, 5, 6, 7%7D)); // 100%0A        System.out.println(prob.maxProfitAssignment(%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%5D%7B2, 4, 6, 8, 10%7D,%0A//            new int%5B%5D%7B10, 5, 30, 40, 50%7D,%0A//            new int%5B%5D%7B4, 5, 6, 7%7D)); // 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   

Solve problem 826