-
Notifications
You must be signed in to change notification settings - Fork 0
/
ActivitySelection.java
45 lines (36 loc) · 1.43 KB
/
ActivitySelection.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
package Greedy_Algorithm_Problems;
import java.util.*;
public class ActivitySelection {
public static void main(String[] args) {
int[] start = {1, 3, 0, 5, 8, 5};
int[] end = {2, 4, 6, 7, 9, 9};
avtivitySelection(start, end);
}
private static void avtivitySelection(int[] start, int[] end) {
// check if the end is sorted (if not sorted do this)
int[][] activities = new int[start.length][3];
for (int i=0; i<start.length; i++){
activities[i][0] = i; // index storing
activities[i][1] = start[i]; // start time storing
activities[i][2] = end[i]; // end time storing
}
Arrays.sort(activities, Comparator.comparingDouble(o -> o[2])); //sorted according to end column
ArrayList<Integer> order = new ArrayList<>();
int maxAct = 1;
// int s = activities[0][1];
int e = activities[0][2];
order.add(0); // storing index in arraylist
for (int i=1; i<end.length; i++){
if (activities[i][1] >= e){
maxAct += 1;
order.add(i);
e = activities[i][2];
}
}
System.out.println("Maximum number of activities : " + maxAct);
for (int i=0; i<order.size(); i++){
System.out.print("A"+ order.get(i) + " -> ");
}
System.out.print("End");
}
}