# 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

```