Activity Selection scheduling problem

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

Reference

1. https://en.wikipedia.org/wiki/Activity_selection_problem
2. http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Greedy/activity.htm