У нас есть 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; } }
Код можно найти здесь.