Greedy Algorithms : Implementing Lecture Scheduling : Coding Interview

Problem Statement

In a conference, N people from a company XYZ are present to attend maximum number of presentations. Each presentation is scheduled between 8:00 and 8:00. Here the second 8:00 means 8:00 pm. Our task is to assign people to presentations such that the number of unique presentations attended by XYZ as a company is maximised.

Input Format

Input is provided in the form a file (taken as command line argument). The first line contains N i.e # of people. Second line contains M i.e # of presentation on that day. M lines follow each containing start and end time of presentation. Time will be in format of HH:MM.

Output Format

Output : The maximum number of presentations that can be attended.

Sample Input

3 
5 
08:00 08:00 
08:00 08:00 
08:00 08:00 
08:00 08:00 
08:00 08:00

Sample Output

3

Explanation

3 people can attend max 3 presentations for the given timings.

Solution

	import java.util.ArrayList;
	import java.util.Collections;
	import java.util.Comparator;
	import java.util.Scanner;
	import java.util.TreeMap;
	class Person{
	int name;
	int startTime = 0;
	int endTime = 0;
	ArrayList<Integer> presentationsAttended = new ArrayList<>();
	Person(int n){
	this.name = n;
	}
	public int getStartTime() {
	return startTime;
	}
	public int getEndTime() {
	return endTime;
	}
	public void setStartTime(int startTime) {
	this.startTime = startTime;
	}
	public void setEndTime(int endTime) {
	this.endTime = endTime;
	}
	}
	class Presentation{
	int name;
	int startTime;
	int endTime;
	ArrayList<Integer> clashesWith = new ArrayList<Integer>();
	boolean attended;
	public Presentation() {
	}
	Presentation(int n, String sTime, String eTime){
	this.name = n;
	this.attended = false;
	this.startTime = convertStime(sTime);
	this.endTime = convertEtime(eTime);
	}
	int convertStime(String sTime){
	int timeInMins = 0;
	String[] strArr = sTime.split(":");
	int hour = Integer.parseInt(strArr[0]);
	int min = Integer.parseInt(strArr[1]);
	if(hour < 8){
	timeInMins = ((12+hour) * 60) + min ;
	} else {
	timeInMins = (hour * 60) + min;
	}
	return timeInMins;
	}
	int convertEtime(String eTime){
	int timeInMins = 0;
	String[] strArr = eTime.split(":");
	int hour = Integer.parseInt(strArr[0]);
	int min = Integer.parseInt(strArr[1]);
	if(hour == 8 && min != 0){
	timeInMins = (hour * 60) + min;
	} else if( hour <= 8){
	timeInMins = ((12+hour) * 60) + min;
	}else {
	timeInMins = (hour * 60) + min;
	}
	return timeInMins;
	}
	public void setName(int name) {
	this.name = name;
	}
	public int getName() {
	return name;
	}
	public int getStartTime() {
	return startTime;
	}
	public int getEndTime() {
	return endTime;
	}
	public ArrayList<Integer> getClashesWith() {
	return clashesWith;
	}
	public boolean isAttended() {
	return attended;
	}
	public void setAttended(boolean attended) {
	this.attended = attended;
	}
	}
	public class SchedulingFinal {
	public static ArrayList<Presentation> alPrez = new ArrayList<Presentation>();
	public static ArrayList<Person> alPerson = new ArrayList<Person>();
	public static ArrayList<Presentation> attended = new ArrayList<Presentation>();
	public static void main(String[] args) {
	Scanner input = new Scanner(System.in);
	int noOfPeople = input.nextInt();
	int noOfPrez = input.nextInt();
	int count = 0;
	for(int i = 0; i < noOfPrez; i++){
	String startTime = input.next();
	String endTime = input.next();
	Presentation newPrez = new Presentation(i, startTime, endTime);
	alPrez.add(newPrez);
	}
	for(int j = 0; j < noOfPeople; j++){
	Person newPerson = new Person(j);
	alPerson.add(newPerson);
	}
	Collections.sort(alPrez, new sortBystartTime());
	int t = 0;
	for(t = 0; t < noOfPeople ;t ++){
	attended.add(alPrez.get(t));
	count++;
	alPerson.get(t).setStartTime(alPrez.get(t).getStartTime());
	alPerson.get(t).setEndTime(alPrez.get(t).getEndTime());
	}
	for(int d = t; d < alPrez.size(); d++){
	Collections.sort(alPerson, new sortByendTime());
	if(alPrez.get(d).getStartTime() >= alPerson.get(0).getEndTime()){
	count ++;
	alPerson.get(0).setStartTime(alPrez.get(d).getStartTime());
	alPerson.get(0).setEndTime(alPrez.get(d).getEndTime());
	} else if(alPrez.get(d).getEndTime() < alPerson.get(alPerson.size()-1).getEndTime()){
	alPerson.get(alPerson.size()-1).setStartTime(alPrez.get(d).getStartTime());
	alPerson.get(alPerson.size()-1).setEndTime(alPrez.get(d).getEndTime());
	}
	}
	System.out.println(count);
	}
	}
	class sortBystartTime implements Comparator<Presentation>{
	public int compare(Presentation p1, Presentation p2) {
	if(p1.getStartTime()<p2.getStartTime()){
	return -1;
	} else if(p1.getStartTime()>p2.getStartTime()){
	return 1;
	}
	else {
	return 0;
	}
	}
	}
	class sortByendTime implements Comparator<Person>{
	public int compare(Person p1, Person p2) {
	if(p1.getEndTime()< p2.getEndTime()){
	return -1;
	}if(p1.getEndTime()> p2.getEndTime()){
	return 1;
	}else {
	return 0;
	}
	}
	}

view raw lecture-scheduling.java hosted with ❤ by GitHub