Again, I have TLE on CSES using Java. Please let me know if I have the correct algorithm and my TLE is just because of Java? https://cses.fi/problemset/task/1164
What I am doing is using a min-heap (priority queue) in Java to store the end times of customers who already checked in. Then, for each new customer, I will check whether an existing room has opened up. (The end time in the priority queue should be less than the arrival times of the new customer). If there exists such a room, then I poll the element and assign that room ID to the new customer. The total rooms used is just the max room ID I go up to (or the max size of the priority queue of all time).
import java.io.*;
import java.util.*;
public class cses {
static int n;
static boolean[] used;
public static void main(String[] args) throws IOException{
BufferedReader file = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(file.readLine());
PriorityQueue<Point> pq = new PriorityQueue<>();
int[][] times = new int[n][3];
int[] ans = new int[n];
for (int i=0; i<n; i++){
StringTokenizer st = new StringTokenizer(file.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
times[i][0] = start;
times[i][1] = end;
times[i][2] = i;
}
Arrays.sort(times, (a, b) -> a[0]-b[0]);
int rooms = 0;
int max = 0;
for (int i=0; i<n; i++){
int start = times[i][0];
int end = times[i][1];
if (pq.isEmpty()){
rooms++;
pq.add(new Point(end, rooms));
ans[times[i][2]] = rooms;
}else{
if (pq.peek().t < start){
int currid = pq.poll().id;
pq.add(new Point(end, currid));
ans[times[i][2]] = currid;
}else{
rooms++;
pq.add(new Point(end, rooms));
ans[times[i][2]] = rooms;
}
}
max = Math.max(pq.size(), max);
}
System.out.println(max);
for (int i : ans){
System.out.print(i + " ");
}
}
static class Point implements Comparable<Point>{
int id;
int t;
public Point(int t, int id){
this.t = t;
this.id = id;
}
@Override
public int compareTo(Point o) {
return this.t - o.t;
}
}
}