Activity Selection Problem using Greedy-method in Java

There are following  steps we will be taking to solve the activity selection problem using Greedy method in Java,
1: Sort the activities in ascending order according to their finishing time.
2: Select the first activity from sorted array a[] (Whatever you assume) and reupdate it.
3: If the start time of the currently selected activity is greater than or equal to the finish time of the previously selected activity, then print the current activity.
4: Select the next activity in a[] array.
5: Repeat this activity till the last index.

Explanation of activity selection

Activity: a1|a2|a3|a4|a5|a6|
StartTime 0 |3 |1 |5 |5 |8 |
FinishTime6 |4 |2 |9 |7 |9 |
The table after we have sorted it:
------------------
a3|a2|a1|a5|a4|a6|
1 |3 |0 |5 |5 |8 |
2 |4 |6 |7 |9 |9 |
------------------
Final Execution(Number of state=4)
a3--->a2--->a5--->a6

Java Code to solve Activity Selection Problem using Greedy-method

import java.util.*;

class activity_selection
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int n,i,j;
System.out.println("Enter no. of activities");
n=sc.nextInt();
String a[]=new String[n];
int start[]=new int[n];
int finish[]=new int[n];
for(i=0;i<n;i++)
{
System.out.println("Enter activitiy");
a[i]=sc.next();
System.out.println("Enter Start time");
start[i]=sc.nextInt();
System.out.println("Enter Finish time");
finish[i]=sc.nextInt();
}
System.out.println("****ACTIVITY-SELECTION-PROBLEM-CHART****");
System.out.println("------------------");
for(i=0;i<n;i++)
{
System.out.print(a[i]+"|");
}
System.out.println();
for(i=0;i<n;i++)
{
System.out.print(start[i]+" |");
}
System.out.println();
for(i=0;i<n;i++)
{
System.out.print(finish[i]+" |");
}
System.out.println();
System.out.print("------------------");
for(i=0;i<n-1;i++)
    {
        for(j=i+1;j<n;j++)
        {
        if(finish[i]>finish[j])
         {
          int temp=finish[i];
          finish[i]=finish[j];
          finish[j]=temp;
    
          int temp1=start[i];
          start[i]=start[j];
          start[j]=temp1;

          String temp2=a[i];
          a[i]=a[j];
          a[j]=temp2;
         }	
         }
       }
System.out.println();
System.out.println("****ACTIVITY-SELECTION-PROBLEM-AFTER-SORTING-CHART****");
System.out.println("------------------");
for(i=0;i<n;i++)
{
System.out.print(a[i]+"|");
}
System.out.println();
for(i=0;i<n;i++)
{
System.out.print(start[i]+" |");
}
System.out.println();
for(i=0;i<n;i++)
{
System.out.print(finish[i]+" |");
}
System.out.println();
System.out.println("------------------");
System.out.println("FINAL-EXECUTION-CHART");
System.out.print(a[0]);
int x=0;
for(i=1;i<n;i++)
{
if(start[i]>=finish[x])
{
System.out.print("--->"+a[i]);
x=i;
}
}
}
}

OUTPUT

Enter no. of activities
6
Enter activitiy
a1
Enter Start time
0
Enter Finish time
6
Enter activitiy
a2
Enter Start time
3
Enter Finish time
4
Enter activitiy
a3
Enter Start time
1
Enter Finish time
2
Enter activitiy
a4
Enter Start time
5
Enter Finish time
9
Enter activitiy
a5
Enter Start time
5
Enter Finish time
7
Enter activitiy
a6
Enter Start time
8
Enter Finish time
9
****ACTIVITY-SELECTION-PROBLEM-CHART****
------------------
a1|a2|a3|a4|a5|a6|
0 |3 |1 |5 |5 |8 |
6 |4 |2 |9 |7 |9 |
------------------
****ACTIVITY-SELECTION-PROBLEM-AFTER-SORTING-CHART****
------------------
a3|a2|a1|a5|a4|a6|
1 |3 |0 |5 |5 |8 |
2 |4 |6 |7 |9 |9 |
------------------
FINAL-EXECUTION-CHART
a3--->a2--->a5--->a6

Download the files of the code in Java, C

Activity Selection Problem using Greedy-method.zip

Leave a Reply

Your email address will not be published. Required fields are marked *