Activity selection problem in Java
The activity selection problem is a multiple objective problem hat requires choosing non-conflicting tasks to complete within a specific amount of time from a list of tasks identified by a start time (si) and completion time (fi). If a person can only work on one activity at a time, the challenge is to choose the most tasks that a single human or machine can complete.
Non-conflicting activities:
Assume that there are N multiple tasks and that each activity has a launch date (s) and a deadline (f). If s1>=f2 or s2 >=f1, two actions, 1 and 2, are said to have been non-conflicting.
Greedy Approach
The greedy decision is to consistently choose the next action whose start time is greater than or equal to the completion time of the preceding activity and whose finish time is the earliest available activity. The activities can be arranged according to their completion time such that the subsequent action is always thought of as the activity with the earliest completion time.
Algorithm
- Sort all the activities through the time activity ends.
- Please choose the first activity, record the time it ends, and label it current_endtime.
- Continue by repeating the remaining tasks. current activity for each
- if current_activitytime >current_endtime of the start time.
- select current_activitytime parameter.
- Update current_endtime to reflect current_activitytime end time.
- If not, delete the current activity.
Filename: ActivitySelectionProblem.java
//Java program that solves the problem of activity selection.
//The following implementation of the activities are arranged in order of //finish time.
import java.io.*;
import java.lang.*;
import java.util.*;
class ActivitySelectionProblem{
//Displays the activities that can be done at a single time
//By the single person
public static void printMaxActivities(int si[], int fi[],int num)
{
int i, j;
System.out.println("The activities selected are:");
// the initial activity is always selected as it is initial
i = 0;
System.out.print(i + " ");
// The other activities are
for (j = 1; j < num; j++) {
// The activity should be chosen if its start time is greater than or equal to the previously chosen activity.
if (si[j] >= fi[i])
{
System.out.print(j + " ");
i = j;
}
}
// Main section of the program
public static void main(String[] args)
{
int si[] = { 3, 3, 0, 6, 7, 5 };
int fi[] = { 2, 5, 6, 9, 8, 2 };
int num = si.length;
// Function call
printMaxActivities(si, fi, num);
}
}
Output
The activities selected are are:0 1 3
Time complexity: O(n)
Space complexity is: O(1)
Implementation of the unsorted activities
For the implementation of unsorted activities, first, we need to sort the activities based on the ending time of each of the activities.
After that, the greedy algorithm is applied to solve the problem.
Example:
Input:
Array[]={{1,9},{2,8},{4,8},{1,6},{0,5},{6,7}}
The given array Array is sorted according to the completion time
Sorted Array={{0,5},{1,6},{6,7},{2,8},{4,8},{1,9}}
Output:
{(0, 5), (6, 7)}
Program for unsorted activities
Filename: ActivitySelection.java
//Java program for activity selection when activities are not sorted
import java.io.*;
import java.util.*;
// the job having the initial and final time
class ActivityProblem{
int initial, end;
// The ActivityProblem constructor
public ActivityProblem(int initial,int end)
{
this.initial =initial;
this.end = end;
}
}
//comparing the activities
class Compares {
// sorting the activities
static void compares(ActivityProblem array[], int num)
{
Arrays.sort(array, new Comparator<ActivityProblem>() {
@Override
public int compare(ActivityProblem st1, ActivityProblem st2)
{
return st1.end - st2.end;
}
});
}
}
// Main class
class ActivitySelection {
// Displays the possibilities
static void printMaxActivities(ActivityProblem array[], int num)
{
//the jobs are according to the end time
Compares object = new Compares();
object.compares(array, num);
System.out.println("The selected activities");
// The initial activity is selected first
int i = 0;
System.out.print("(" + array[i].initial + ", "+ array[i].end + ")");
// iterating the other activities
for (int j = 1; j < num; j++) {
//The activity should be chosen if its start time is greater //than or equal to the previously chosen //in the list.
if (array[j].initial >= array[i].end) {
System.out.print(", (" + array[j].initial + ", "
+ array[j].end + ")");
i = j;
}
}
}
//Main section
public static void main(String[] args)
{
int num = 6;
ActivityProblem array[] = new ActivityProblem[num];
array[0] = new ActivityProblem(5, 7);
array[1] = new ActivityProblem(1, 6);
array[2] = new ActivityProblem(8, 5);
array[3] = new ActivityProblem(1, 0);
array[4] = new ActivityProblem(9, 9);
array[5] = new ActivityProblem(7, 1);
// function calling
printMaxActivities(array, num);
}
}
Output
The selected activities(1, 0), (7, 1), (8, 5), (5, 7), (9, 9)
Time Complexity=O(N Log N)
Space Complexity=O(1)
Using Priority Queue
To solve that problem, follow the instructions given:
- Push the activities onto the priority queue (Min-Heap).
- Place the first activity in the priority at the beginning of the response vector. Set the parameters to start and end to the first activity's beginning and completion times, respectively.
- Perform the following when the priority is not zero:
- Check the first spot in the priority line.
- Push this activity into the response vector if its start time is larger than or equal to the end time of the previous one.
- Aside from that, disregard it.
- Print the selected actions that are saved in the response vector.
Filename: ActivitySelection.java
// Java program for activity selection
//importing required packages
import java.io.*;
import java.lang.*;
import java.util.*;
class ActivitySelection{
// the pairs of the class
static class Pairs {
int firsts;
int seconds;
Pairs(int firsts, int seconds)
{
this.firsts = firsts;
this.seconds = seconds;
}
}
static void SelectActivity(int st[], int ft[])
{
// Vector for storing the result
ArrayList<Pairs> anss = new ArrayList<>();
// sorting of the pairs
PriorityQueue<Pairs> pair = new PriorityQueue<>((p1, p2) -> p1.firsts - p2.firsts);
for (int i = 0; i < st.length; i++) {
// the elements are added to the queue
pair.add(new Pairs(ft[i],st[i]));
}
Pairs ite = pair.poll();
int starts = ite.seconds;
int ends = ite.firsts;
anss.add(new Pairs(starts, ends));
while (!pair.isEmpty()) {
Pairs itre = pair.poll();
if (itre.seconds >= ends) {
starts = itre.seconds;
ends = itre.firsts;
anss.add(new Pairs(starts, ends));
}
}
System.out.println("The activities which are selected \n");
for (Pairs itre : anss) {
System.out.println("The Activity began at " + itre.firsts+ " and it completed at " + itre.seconds);
}
}
// Main section
public static void main(String[] args)
{
int st[] = { 3, 3, 0, 1, 2, 8 };
int ft[] = { 4, 0, 6, 2, 1, 4 };
// Function call
SelectActivity(st, ft);
}
}
Output
The activities which are selected
The Activity began at 3 and it completed at 0
The Activity began at 2 and it completed at 1
The Activity began at 1 and it completed at 2
The Activity began at 3 and it completed at 4
The Activity began at 8 and it completed at 4
Time Complexity=O(N *log N)
Space Complexity=O(N)