????????給定一個作業數組，其中每個作業都有一個截止期限，如果作業在截止期限之前完成，則可獲得相關利潤。此外，每個作業都占用一個單位時間，因此任何作業的最小可能截止期限都是 1。如果一次只能安排一項作業，則最大化總利潤。

例子：?
輸入：四個工作，截止日期和利潤如下
JobID 截止期限 利潤
? 一 4 20 ??
? 二 1 10
? 三 1 40 ?
? 四 1 30

輸出：以下是工作利潤最大的序列：c、a ??

輸入： ?五項工作，截止日期和利潤如下

JobID 截止期限 利潤

? a 2 100
? b 1 19
? c 2 27
? d 1 25
? e 3 15

輸出：以下是工作利潤最大的序列：c，a，e

樸素方法：要解決問題，請遵循以下想法：

生成給定作業集的所有子集，并檢查各個子集是否可行。跟蹤所有可行子集中的最大利潤。

作業排序問題的貪婪方法：
貪婪地首先選擇利潤最高的工作，方法是按利潤降序對工作進行排序。這將有助于最大化總利潤，因為為每個時間段選擇利潤最高的工作最終將最大化總利潤

按照給定的步驟解決問題：

按利潤的降序對所有工作進行排序。?
按利潤遞減的順序對工作進行迭代。對于每項工作，執行以下操作：?
找到一個時間段 i，使得時間段為空、i < 截止時間且 i 最大。將作業放入?
此時間段并將此時間段標記為已填充。?
如果不存在這樣的 i，則忽略該工作。?
下面是上述方法的實現：?

// Java code for the above approach?
?
import java.util.*;
?
class Job {
? ?
? ? // Each job has a unique-id,profit and deadline
? ? char id;
? ? int deadline, profit;
?
? ? // Constructors
? ? public Job() {}
?
? ? public Job(char id, int deadline, int profit)
? ? {
? ? ? ? this.id = id;
? ? ? ? this.deadline = deadline;
? ? ? ? this.profit = profit;
? ? }
?
? ? // Function to schedule the jobs take 2 arguments
? ? // arraylist and no of jobs to schedule
? ? void printJobScheduling(ArrayList<Job> arr, int t)
? ? {
? ? ? ? // Length of array
? ? ? ? int n = arr.size();
? ? ? ?
? ? ? ? // Sort all jobs according to decreasing order of
? ? ? ? // profit
? ? ? ? Collections.sort(arr,
? ? ? ? ? ? ? ? ? ? ? ? ?(a, b) -> b.profit - a.profit);
?
? ? ? ? // To keep track of free time slots
? ? ? ? boolean result[] = new boolean[t];
?
? ? ? ? // To store result (Sequence of jobs)
? ? ? ? char job[] = new char[t];
?
? ? ? ? // Iterate through all given jobs
? ? ? ? for (int i = 0; i < n; i++) {
? ? ? ? ? ? // Find a free slot for this job (Note that we
? ? ? ? ? ? // start from the last possible slot)
? ? ? ? ? ? for (int j
? ? ? ? ? ? ? ? ?= Math.min(t - 1, arr.get(i).deadline - 1);
? ? ? ? ? ? ? ? ?j >= 0; j--) {
? ? ? ? ? ? ? ? // Free slot found
? ? ? ? ? ? ? ? if (result[j] == false) {
? ? ? ? ? ? ? ? ? ? result[j] = true;
? ? ? ? ? ? ? ? ? ? job[j] = arr.get(i).id;
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
?
? ? ? ? // Print the sequence
? ? ? ? for (char jb : job)
? ? ? ? ? ? System.out.print(jb + " ");
? ? ? ? System.out.println();
? ? }
?
? ? // Driver's code
? ? public static void main(String args[])
? ? {
? ? ? ? ArrayList<Job> arr = new ArrayList<Job>();
? ? ? ? arr.add(new Job('a', 2, 100));
? ? ? ? arr.add(new Job('b', 1, 19));
? ? ? ? arr.add(new Job('c', 2, 27));
? ? ? ? arr.add(new Job('d', 1, 25));
? ? ? ? arr.add(new Job('e', 3, 15));
?
? ? ? ? System.out.println(
? ? ? ? ? ? "Following is maximum profit sequence of jobs");
?
? ? ? ? Job job = new Job();
?
? ? ? ? // Function call
? ? ? ? job.printJobScheduling(arr, 3);
? ? }
}
?
// This code is contributed by Aditya Kumar (adityakumar129)??

輸出
以下是工作的最大利潤序列

c a e?

計算機輔助設計
時間復雜度： O(N 2 )
輔助空間： O(N)

使用優先級隊列（最大堆）的作業排序問題：
按截止日期的升序對作業進行排序，然后從末尾開始迭代，計算每兩個連續截止日期之間的可用時隙。當空時隙可用且堆不為空時，將作業的利潤包含在最大堆的根部，因為這有助于為每組可用時隙選擇利潤最大的作業。

下面是上述方法的實現：

// Java implementation of above approach
?
// Program to find the maximum profit
// job sequence from a given array
// of jobs with deadlines and profits
import java.util.*;
?
public class GFG {
?
? ? // a class to represent job
? ? static class Job {
? ? ? ? char job_id;
? ? ? ? int deadline;
? ? ? ? int profit;
? ? ? ? Job(char job_id, int deadline, int profit)
? ? ? ? {
? ? ? ? ? ? this.deadline = deadline;
? ? ? ? ? ? this.job_id = job_id;
? ? ? ? ? ? this.profit = profit;
? ? ? ? }
? ? }
?
? ? static void printJobScheduling(ArrayList<Job> arr)
? ? {
? ? ? ? int n = arr.size();
?
? ? ? ? // sorting the array on the
? ? ? ? // basis of their deadlines
? ? ? ? Collections.sort(arr, (a, b) -> {
? ? ? ? ? ? return a.deadline - b.deadline;
? ? ? ? });
?
? ? ? ? // initialise the result array and maxHeap
? ? ? ? ArrayList<Job> result = new ArrayList<>();
? ? ? ? PriorityQueue<Job> maxHeap = new PriorityQueue<>(
? ? ? ? ? ? (a, b) -> { return b.profit - a.profit; });
?
? ? ? ? // starting the iteration from the end
? ? ? ? for (int i = n - 1; i > -1; i--) {
? ? ? ? ? ? int slot_available;
? ? ? ? ? ?
? ? ? ? ? ? // calculate slots between two deadlines
? ? ? ? ? ? if (i == 0) {
? ? ? ? ? ? ? ? slot_available = arr.get(i).deadline;
? ? ? ? ? ? }
? ? ? ? ? ? else {
? ? ? ? ? ? ? ? slot_available = arr.get(i).deadline
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?- arr.get(i - 1).deadline;
? ? ? ? ? ? }
?
? ? ? ? ? ? // include the profit of job(as priority),
? ? ? ? ? ? // deadline and job_id in maxHeap
? ? ? ? ? ? maxHeap.add(arr.get(i));
?
? ? ? ? ? ? while (slot_available > 0
? ? ? ? ? ? ? ? ? ?&& maxHeap.size() > 0) {
?
? ? ? ? ? ? ? ? // get the job with max_profit
? ? ? ? ? ? ? ? Job job = maxHeap.remove();
?
? ? ? ? ? ? ? ? // reduce the slots
? ? ? ? ? ? ? ? slot_available--;
?
? ? ? ? ? ? ? ? // include the job in the result array
? ? ? ? ? ? ? ? result.add(job);
? ? ? ? ? ? }
? ? ? ? }
?
? ? ? ? // jobs included might be shuffled
? ? ? ? // sort the result array by their deadlines
? ? ? ? Collections.sort(result, (a, b) -> {
? ? ? ? ? ? return a.deadline - b.deadline;
? ? ? ? });
? ? ? ?
? ? ? ? for (Job job : result) {
? ? ? ? ? ? System.out.print(job.job_id + " ");
? ? ? ? }
? ? ? ?
? ? ? ? System.out.println();
? ? }
?
? ? // Driver's Code
? ? public static void main(String[] args)
? ? {
? ? ? ? ArrayList<Job> arr = new ArrayList<Job>();
?
? ? ? ? arr.add(new Job('a', 2, 100));
? ? ? ? arr.add(new Job('b', 1, 19));
? ? ? ? arr.add(new Job('c', 2, 27));
? ? ? ? arr.add(new Job('d', 1, 25));
? ? ? ? arr.add(new Job('e', 3, 15));
? ? ? ?
? ? ? ? System.out.println("Following is maximum "
? ? ? ? ? ? ? ? ? ? ? ? ? ?+ "profit sequence of jobs");
?
? ? ? ? // Function call
? ? ? ? printJobScheduling(arr);
? ? }
}
?
// This code is contributed by Karandeep Singh?

輸出
以下是作業的最大利潤序列

a c e?

時間復雜度： O(N log N)
輔助空間： O(N)?