My code is inspired by the following article which contains the code-sample which determines the maximum number of activities that can be performed using a greedy algorithm.

I am treating the problem differently with respect to the greedy idea. I would like to begin at the Earliest Start Time and only then let the greedy algorithm to determine the optimal solution (i.e. non-overlapping pairs beginning from the Earliest Start Time).

I'm using PriorityQueue because I'm treating the input as unsorted.

I'm curious to know how to choose the activity having the Earliest Start Time and proceed with maximum number of non-overlapping pairs (activities)?

My code:

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);
  }
}

Current output:

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

Desired output:

Following Activities should be selected. 

Activity started at: 0 and ends at  6
Activity started at: 8 and ends at  9

CodePudding user response：

In order to always start with the earliest task and then pick the rest tasks in such a way that the number of the fulfilled tasks would be maximal, firstly we need to determine the earliest task and then apply a greedy approach to maximize the total number of tasks.

The problem can be addressed in the following steps:

• Parse the pair of given arrays and create a queue of tasks.

• Find the earliest task and remove it from the queue.

• Apply a greedy algorithm to find the rest tasks.

• Print the list of tasks.

For conciseness to represent a task, I'm using Java 16 record (you can substitute with a class).

That's how it can be implemented:

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 });
}

Output:

Activity has started at: 0 and ended at 6
Activity has started at: 8 and ended at 9

CodePudding user response：

Isn't it selecting the earliest start time already? Because that is the concept of Greedy. You take the earliest available task with the highest bounty/reward.