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
Leave a Reply