Skip to content

Instantly share code, notes, and snippets.

@thmain
Last active June 6, 2023 03:57
Show Gist options
  • Save thmain/f6b77bc6bf85397e53df8f5c1d6a925f to your computer and use it in GitHub Desktop.
Save thmain/f6b77bc6bf85397e53df8f5c1d6a925f to your computer and use it in GitHub Desktop.
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
class Lecture {
int startTime;
int endTime;
public Lecture(int startTime, int endTime) {
this.startTime = startTime;
this.endTime = endTime;
}
}
public class MinimumHallsOptimzed {
public static int minHalls(List<Lecture> lectures) {
List<Integer> startTimes = new ArrayList<>();
List<Integer> endTimes = new ArrayList<>();
for (Lecture lecture : lectures) {
startTimes.add(lecture.startTime);
endTimes.add(lecture.endTime);
}
Collections.sort(startTimes);
Collections.sort(endTimes);
int startPtr = 0;
int endPtr = 0;
int halls = 0;
int currentHalls = 0;
while (startPtr < startTimes.size()) {
if (startTimes.get(startPtr) < endTimes.get(endPtr)) {
currentHalls++;
startPtr++;
} else {
currentHalls--;
startPtr++;
endPtr++;
}
halls = Math.max(halls, currentHalls);
}
return halls;
}
public static void main(String[] args) {
List<Lecture> lectures = new ArrayList<>();
lectures.add(new Lecture(9, 10));
lectures.add(new Lecture(10, 11));
lectures.add(new Lecture(11, 12));
lectures.add(new Lecture(9, 12));
int minimumHalls = minHalls(lectures);
System.out.println("Minimum number of halls required: " + minimumHalls);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment