An activity-selection is the problem of scheduling a resource among several competing activity. It is a mathematical optimization problem concerning the selection of non-conflicting activities to perform within a given time frame, given a set of activities each marked by a start time and finish time.
The problem is to select the maximum number of activities that can be performed by a single person or machine, assuming that a person can only work on a single activity at a time. Write a program to activity selection problem?
source Code
package com.dsacode.Algorithm.greedy; import java.util.Arrays; public class MaxActivities { private static void printMaxActivities(int startTime[], int finishTime[], int size) { int i, j; System.out.println("Following activities are selected"); i = 0; print(i,startTime[i],finishTime[i]); for (j = 1; j < size; j++) { if (startTime[j] >= finishTime[i]) { i = j; print(j,startTime[j],finishTime[j]); } } } private static void print(int nthPosition, int startTime, int finishTime){ System.out.println(nthPosition+ " th Acticivity is selected which has start time of [" + startTime + "] and finish time of [" + finishTime + "]"); } public static void main(String[] args) { int s[] = { 1, 3, 0, 5, 8, 5 }; int f[] = { 2, 4, 6, 7, 9, 9 }; System.out.println("Array 1 items : " + Arrays.toString(s)); System.out.println("Array 2 items : " + Arrays.toString(f)); int size = s.length; printMaxActivities(s, f, size); } }
Output
Array 1 items : [1, 3, 0, 5, 8, 5] Array 2 items : [2, 4, 6, 7, 9, 9] Following activities are selected 0 th Acticivity is selected which has start time of [1] and finish time of [2] 1 th Acticivity is selected which has start time of [3] and finish time of [4] 3 th Acticivity is selected which has start time of [5] and finish time of [7] 4 th Acticivity is selected which has start time of [8] and finish time of [9]
Algorithm Explanation
![]() | Sort the activities according to their finishing time |
![]() | Select the first activity from the sorted array and print it. |
![]() | If the start time of this activity is greater than the finish time of previously selected activity then select this activity and print it. |
Time Complexity
Best Case | Average Case | Worst Case |
---|---|---|
– | O(nlgn) | – |