最大化任务数量，以使第一个任务的开始时间始终是最早的

Question

我的代码灵感来自以下 包含代码样本，该代码样本决定使用贪婪算法可以执行的最大活动数量。

关于贪婪的想法，我对问题的对待有所不同。我想从最早的开始时间开始，然后才能让贪婪的算法确定最佳解决方案（即从最早的开始时间开始的非重叠对）。

我正在使用PriortityQueue，因为我将输入视为未分类。

我很想知道如何选择最早的开始时间的活动，并进行最大数量的非重叠对（活动）？

我的代码：

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

Answer 1

为了始终从最早的任务开始，然后选择以使得满足任务的数量最大的方式选择其余任务，首先我们需要确定最早的任务，然后采用贪婪的方法来最大化任务总数。

问题可以在以下步骤中解决：

• 解析给定数组对并创建任务队列。

• 找到最早的任务并将其从队列中删除。

• 应用贪婪算法查找其余任务。

• 打印任务列表。

为了简明性表示 task ，我正在使用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

Answer 2

它不是选择最早的开始时间吗？因为那是贪婪的概念。您要采取最早的赏金/奖励的最早任务。