I am getting TLE for this problem https://www.codechef.com/START1C/problems/ADMIT
Below is my code. can anyone help me out?
I Have added few comments to explain my approach.
class CollegeAdmission {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
int T = Integer.parseInt(br.readLine());
while(T–>0) {
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[] collegeRank = new int[n];
st = new StringTokenizer(br.readLine());
for(int i=0; i<n; i++)
collegeRank[i] = Integer.parseInt(st.nextToken());int[] studentRank = new int[m]; st = new StringTokenizer(br.readLine()); for(int i=0; i<m; i++) studentRank[i] = Integer.parseInt(st.nextToken()); // List of List of college preference of students ArrayList<ArrayList<Integer>> preferences = new ArrayList<>(m); for(int i=0; i<m; i++) { st = new StringTokenizer(br.readLine()); int k = Integer.parseInt(st.nextToken()); // List of preference of particular student ArrayList<Integer> preference = new ArrayList<>(k); for(int j=0; j<k; j++) preference.add(Integer.parseInt(st.nextToken()) - 1); // minus 1 to match zero based indexing of college Id //sorting preference of student based on college rank preference.sort(Comparator.comparingInt(e -> collegeRank[e])); preferences.add(preference); } pw.println(getCollege(n,m,collegeRank,studentRank,preferences)); } pw.close(); }
private static int getCollege(int n, int m, int[] collegeRank, int[] studentRank, ArrayList<ArrayList> preferences) {
// Track if college is available
boolean[] isAvailable = new boolean[n];
Arrays.fill(isAvailable,true);// Sorting student Ids based on their rank Integer [] studIdByRank = new Integer[m]; for(int i=0; i<m; i++) studIdByRank[i] = i; Arrays.sort(studIdByRank, Comparator.comparingInt(e -> studentRank[e])); int chefRank = studentRank[0]; for(int i=0; i<m && studentRank[studIdByRank[i]] <= chefRank; i++) { int stud_id = studIdByRank[i]; for(int j=0; j<preferences.get(stud_id).size(); j++) { int coll_id = preferences.get(stud_id).get(j); if(isAvailable[coll_id]){ isAvailable[coll_id] = false; if(stud_id == 0) return coll_id+1; break; } } } return 0; }