У нас есть n работа, каждая из которых должна быть выполнена с startTime[i] по endTime[i], с получением profit[i] прибыли.

Вам даны массивы startTime, endTime и profit, вам нужно вывести максимальную прибыль, которую вы можете получить, чтобы в подмножестве не было двух заданий с перекрывающимся временным диапазоном.

Если вы выберете задание, которое заканчивается в время X, вы сможете начать другое задание, которое начнется в время X.

Пример 1:

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120
Explanation: The subset chosen is the first and fourth job. 
Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.

Пример 2:

Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
Output: 150
Explanation: The subset chosen is the first, fourth and fifth job. 
Profit obtained 150 = 20 + 70 + 60.

Пример 3:

Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
Output: 6

Ограничения:

  • 1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4
  • 1 <= startTime[i] < endTime[i] <= 10^9
  • 1 <= profit[i] <= 10^4

Решение:

Мы будем решать эту проблему с помощью динамического программирования. Вот объяснение с примером:

Вот мой Java-код:

public class MaximumProfitJobScheduling {
    public class Task {
        public int start;
        public int end;
        public int profit;

        public Task(int start, int end, int profit) {
            this.start = start;
            this.end = end;
            this.profit = profit;
        }
    }

    public static void main(String[] args) {
       /* MaximumProfitJobScheduling maximumProfitJobScheduling = new MaximumProfitJobScheduling();
        int result = maximumProfitJobScheduling.jobScheduling(
                new int[]{1, 2, 3, 3},
                new int[]{3, 4, 5, 6},
                new int[]{50, 10, 40, 70});
        System.out.println(result);*/

       /* MaximumProfitJobScheduling maximumProfitJobScheduling = new MaximumProfitJobScheduling();
        int result = maximumProfitJobScheduling.jobScheduling(
                new int[]{1, 2, 3, 4, 6},
                new int[]{3, 5, 10, 6, 9},
                new int[]{20, 20, 100, 70, 60});
        System.out.println(result);*/
        MaximumProfitJobScheduling maximumProfitJobScheduling = new MaximumProfitJobScheduling();
        int result = maximumProfitJobScheduling.jobScheduling(
                new int[]{4, 2, 4, 8, 2},
                new int[]{5, 5, 5, 10, 8},
                new int[]{1, 2, 8, 10, 4});
        System.out.println(result);
    }

    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        List<Task> tasks = new ArrayList<>();
        for (int i = 0; i < profit.length; i++) {
            tasks.add(new Task(startTime[i], endTime[i], profit[i]));
        }
        Collections.sort(tasks, (u, v) -> {
            if (u.end > v.end) return 1;
            else if (u.end < v.end) return -1;
            else return 0;
        });

        Map<Integer, List<Task>> map = new HashMap<>();
        int maxTask = 0;
        for (Task t : tasks) {
            maxTask = Math.max(maxTask, t.end);
            map.compute(t.end, (k, v) -> v == null ? new ArrayList<Task>() : v).add(t);
        }
        int[] cache = new int[maxTask + 1];

        int maxProfit = 0;
        for (int i = 1; i < cache.length; i++) {
            List<Task> tList = map.get(i);
            if (tList == null)
                cache[i] = cache[i - 1];
            else {
                cache[i] = cache[i - 1];
                for (Task t : tList) {
                    cache[i] = Math.max(cache[i], t.profit + cache[t.start]);
                }
            }
            maxProfit = Math.max(maxProfit, cache[i]);
        }
        return maxProfit;
    }
}

Код можно найти здесь.