Greedy Approachs

activitySelection.java

import java.io.*;
import java.util.*;
// @Author: Vaib
// Activity Selection
// Greedy Algorithm - #1
// Given start and end times of different activites. A person has to select max number of activites that can be done (no two at same time)

class activitySelection {
  static void maxActivities(int s[],int e[]){
    int activites[][] = new int[s.length][3];
    for (int i = 0; i < activites.length; i++) {
      activites[i][0] = i;
      activites[i][1] = s[i];
      activites[i][2] = e[i];
    }
    // Sorting on the basis of endtime
    Arrays.sort(activites, Comparator.comparingDouble(o -> o[2]));
    int endOfLast = 0;
    ArrayList<Integer> ans = new ArrayList<>();
    for(int i=0;i<s.length;i++){
      if(activites[i][1]>=endOfLast){
        endOfLast = activites[i][2];
        ans.add(activites[i][0]);
      }
    }
    System.out.print(ans.size() + " activites: ");
    for(int i=0;i<ans.size();i++){
      System.out.print(ans.get(i)+" ");
    }
  }
  public static void main(String[] args) {
    int start[] = {1,3,0,5,8,5};
    int end[] = {2,4,6,7,9,9};
    maxActivities(start, end);
  }
}