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)