Job Sequencing Problem in Java

作业排序问题涉及安排具有截止日期的作业以最大化利润。每项作业都有特定的截止日期和相关的利润。目标是确定要完成作业的最佳顺序，在遵守各自截止日期的同时确保最大利润。这个问题可以使用贪心算法来解决。

作业调度示例

输入

作业：(作业 ID, 截止日期, 利润)

(1, 4, 20), (2, 1, 10), (3, 1, 40), (4, 1, 30)

输出

作业顺序：3 1

总利润：60

解释

在作业排序问题中，作业根据其截止日期和利润进行调度。通过优先考虑利润较高的作业，我们可以最大化总利润，同时确保每项作业都在其截止日期前完成。在给定的示例中，选择了作业 3 和 1，总利润为 60。

方法 1：使用贪心算法

算法

步骤 1：按利润对作业进行排序：首先，根据利润将作业按降序排序。这样做的目的是首先考虑利润最高的作业，这给了我们最大化总利润的机会。

步骤 2：初始化数据结构：创建一个数组（槽）来跟踪每项可用作业的时间槽。数组的大小等于作业的数量。最初，所有槽都是空的（用 -1 表示）。

步骤 3：遍历作业：从利润最高的作业开始，尝试将其安排在其截止日期前的最后一个可用槽中。这是因为我们希望最大化可用时间槽的使用，从最后一个开始。

步骤 4：检查可用槽：对于每项作业，从其截止日期开始向后检查时间槽。作业将在其截止日期前的第一个可用槽（空）中进行调度。

步骤 5：调度作业：如果找到可用槽，则将作业放入该槽并将其标记为已占用。然后，将作业的利润添加到总利润中。

步骤 6：重复处理所有作业：对排序列表中的每个作业重复此过程。如果作业无法调度（在其截止日期前没有可用槽），则简单地继续处理下一项作业。

步骤 7：输出结果：处理完所有作业后，输出作业顺序以及通过调度选定的作业所赚取的总利润。

文件名：JobSequencing.java

输出

 
Job sequence: 
3 1 
Total Profit: 60   

复杂度分析

时间复杂度

作业排序问题算法的时间复杂度主要由排序步骤决定，即 O(nlogn)，其中 n 是作业的数量。随后的作业调度步骤涉及遍历作业和检查可用槽，这需要 O(n) 的时间，因此总体时间复杂度为 O(nlogn)。

空间复杂度

作业排序问题的空间复杂度为 O(n)，其中 n 是作业的数量。这是因为需要存储作业数组和槽数组。两个数组的大小都与作业的数量成比例，因此总体空间复杂度是线性的。

方法 2：使用并查集 (DSU)

并查集 (DSU) 方法通过使用并查操作来管理可用时间槽，从而有效地调度作业。通过将截止日期视为不相交的集合，它能为每项作业找到最后一个可用槽。这种方法减少了检查多个槽的开销，确保了在截止日期内最大化利润的流程得到简化。

算法

步骤 1：按利润对作业进行排序：首先，根据利润将给定的作业按降序排序。这确保了利润较高的作业会首先被考虑，从而在调度早期阶段最大化总利润。

步骤 2：初始化 DSU 结构：确定所有作业中的最大截止日期。创建一个大小等于该最大截止日期加一的父数组。此数组将跟踪可用时间槽。将父数组中的每个槽初始化为指向自身。这意味着每个槽最初都是空闲的，并充当其代表。

步骤 3：遍历作业：遍历已排序的作业列表。对于每项作业，找到可以调度而不会违反其截止日期的最后一个可用槽。使用 DSU 的 find 操作来查找对应于作业截止日期的槽的父项（代表项）。

步骤 4：调度作业：如果找到有效槽（即槽的代表项大于 0），则在该槽中调度作业。将作业的利润添加到总利润中。

步骤 5：合并槽：调度完作业后，使用 union 操作将当前槽与前一个槽合并。这确保了将来的作业只会检查仍然可用的槽，从而保持高效的调度。

步骤 6：输出结果：处理完所有作业后，父数组将指示哪些槽已被使用。提取并打印调度的作业顺序和赚取的总利润。

文件名：JobSequencingWithDSU.java

输出

 
Job sequence: 
3 1 
Total Profit: 60   

复杂度分析

时间复杂度

时间复杂度为 O(nlogn)，主要由按利润对作业进行排序决定。每项作业调度都涉及 O(α(n)) 的并查集 find 和 union 操作，其中 α(n) 接近常数。这使得即使对于大型输入也能进行高效调度，结合了排序和 DSU 操作。

空间复杂度

空间复杂度为 O(n)，其中 n 是作业的数量。它包括用于跟踪可用槽的并查集 (DSU) 结构中使用的父数组以及一些附加变量。由于没有使用大小显著的额外数据结构，因此空间使用率保持高效且呈线性。