我的代碼受到以下文章的啟發，其中包含確定使用貪心演算法可以執行的最大活動數的代碼示例。
關于貪婪的想法，我正在以不同的方式處理這個問題。我想從最早的開始時間開始，然后才讓貪心演算法來確定最佳解決方案（即從最早的開始時間開始的非重疊對）。
我正在使用PriorityQueue，因為我將輸入視為未排序。
我很想知道如何選擇具有最早開始時間的活動并繼續進行最大數量的非重疊對（活動）？
我的代碼：
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG {
// Pair class
static class Pair {
int first;
int second;
Pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
static void SelectActivities(int s[], int f[])
{
// Vector to store results.
ArrayList<Pair> ans = new ArrayList<>();
// Minimum Priority Queue to sort activities in
// ascending order of finishing time (f[i]).
PriorityQueue<Pair> p = new PriorityQueue<>(
(p1, p2) -> p1.first - p2.first);
for (int i = 0; i < s.length; i ) {
// Pushing elements in priority queue where the
// key is f[i]
p.add(new Pair(f[i], s[i]));
}
Pair it = p.poll();
int start = it.second;
int end = it.first;
ans.add(new Pair(start, end));
while (!p.isEmpty()) {
Pair itr = p.poll();
if (itr.second >= end) {
start = itr.second;
end = itr.first;
ans.add(new Pair(start, end));
}
}
System.out.println(
"Following Activities should be selected. \n");
for (Pair itr : ans) {
System.out.println(
"Activity started at: " itr.first
" and ends at " itr.second);
}
}
// Driver Code
public static void main(String[] args)
{
int s[] = { 1, 3, 0, 5, 8, 5 };
int f[] = { 2, 4, 6, 7, 9, 9 };
// Function call
SelectActivities(s, f);
}
}
電流輸出：
Following Activities should be selected.
Activity started at: 1 and ends at 2
Activity started at: 3 and ends at 4
Activity started at: 5 and ends at 7
Activity started at: 8 and ends at 9
期望的輸出：
Following Activities should be selected.
Activity started at: 0 and ends at 6
Activity started at: 8 and ends at 9
uj5u.com熱心網友回復：
為了總是從最早的任務開始，然后以這樣的方式選擇剩余的任務，使得完成的任務數量最大，首先我們需要確定最早的任務，然后應用貪心方法來最大化總任務數任務。
該問題可以通過以下步驟解決：
決議一對給定的陣列并創建一個任務佇列。
找到最早的任務并將其從佇列中洗掉。
應用貪心演算法來查找其余任務。
列印任務串列。
為了簡潔表示任務，我使用 Java 16 記錄（您可以用類替換）。
這就是它的實作方式：
public record Task(int start, int finish) {}
public static void selectActivities(int[] start, int[] finish) {
if (start.length == 0 || start.length != finish.length) {
return; // throw an exception
}
Queue<Task> tasks = createTasks(start, finish);
Task earliest = pickEarliest(tasks);
List<Task> fulfilledTasks = getFulfilledTasks(tasks, earliest);
printFulfilledTasks(fulfilledTasks);
}
public static Queue<Task> createTasks(int[] start, int[] finish) {
Queue<Task> tasks = new PriorityQueue<>(Comparator.comparingInt(Task::finish));
for (int i = 0; i < start.length; i ) {
tasks.add(new Task(start[i], finish[i]));
}
return tasks;
}
public static Task pickEarliest(Queue<Task> tasks) {
Task earliest = null;
for (Task task: tasks) {
if (earliest == null || task.start() < earliest.start()) {
earliest = task;
}
}
tasks.remove(earliest);
return earliest;
}
public static List<Task> getFulfilledTasks(Queue<Task> tasks, Task earliest) {
List<Task> result = new ArrayList<>();
result.add(earliest);
Task current = earliest;
while (!tasks.isEmpty()) {
Task next = tasks.remove();
if (next.start() >= current.finish()) {
result.add(next);
current = next;
}
}
return result;
}
public static void printFulfilledTasks(List<Task> tasks) {
selectActivities(new int[]{ 1, 3, 0, 5, 8, 5 }, new int[]{ 2, 4, 6, 7, 9, 9 });
}
輸出：
Activity has started at: 0 and ended at 6
Activity has started at: 8 and ended at 9
uj5u.com熱心網友回復：
它不是已經選擇了最早的開始時間嗎？因為那是貪婪的概念。您將獲得最高賞金/獎勵的最早可用任務。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/498187.html
下一篇：最長回文查找演算法的時間復雜度