그리디 - 백준1931 회의실 배정

첫번째 시도
그냥 일단 바선생 풀이 참고하여 구현해봄

import java.io.*;
import java.util.*;
public class Backjoon1931 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] meetings = new int[n][2];
        StringTokenizer st;
        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            meetings[i][0] = start;
            meetings[i][1] = end;
        }
        Arrays.sort(meetings, (o1, o2) ->{
            if(o1[0] < o2[0]){
                return -1;
            }else if(o1[0] > o2[0]){
                return 1;
            }else return 0;
        });
        int cnt = 0;
        int nowIndex = 0;
        int endTime = 0;
        int lastMinIndex = -1;
        while(nowIndex < n){
        	//지금 실행가능한 것 찾기 _정렬후 다음 것
            //현재회의가(nowIndex) 이전 회의 Index보다 작거나같거나, 현재회의의 시작시간이 이전 회의가 끝난 시간보다 빠르면 continue
            if(nowIndex <= lastMinIndex || meetings[nowIndex][0] < endTime){
                nowIndex++;
                continue;
            }
            //가장 빨리끝나는 회의 index 찾기
            int min = 2147483647;
            int minIndex = -1;
            for(int i = nowIndex; i < n; i++){
                if(meetings[i][1] < min){
                    min = meetings[i][1];
                    minIndex = i;
                    lastMinIndex = i;
                }
            }
            //갯수 카운트 후 끝난 시간 기록
            cnt++;
            endTime = meetings[minIndex][1];
            nowIndex++;
        }
        System.out.println(cnt);
    }
}

답은 맞으나 시간초과

정답풀이
위 코드의 시간복잡도를 더 짧게 간결하게 작성하는 방법이 있다.
위에서는 시작시간 순서로 정렬한 후, 끝나는 시간이 가장 빠른 회의시간을 찾는다.
이 때 끝나는 시간이 가장 빠른 회의시간을 찾는데에 다시 시간복잡도 n이 소요되어, 총 n제곱의 시간복잡도를 갖는다.
하지만 여기서 애초에 시작시간 순서로 정렬할 필요 없이, 끝나는 시간 순서로 정렬하여 실행하면 끝나는 시간이 가장 빠른 회의시간을 찾을 필요가 사라진다. 시작시간은 고려할 필요가 없었던 것이다.
대신, 끝나는 시간이 같은 케이스에서는 시작시간이 더 빠른 순서로 정렬되도록 해주어야 한다. 왜냐하면 다음과 같은 반례 때문이다.
4
1 1
2 2 -> 여기서 끝난 시간이 2
1 2 -> 시작하는 시간이 이전에 끝난 시간보다 빠르므로 continue가 실행된다.
2 3

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] meetings = new int[n][2];
        StringTokenizer st;
        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            meetings[i][0] = start;
            meetings[i][1] = end;
        }
        Arrays.sort(meetings, (o1, o2) ->{
            int output;
            if(o1[1] < o2[1]){
                output = -1;
            }else if (o1[1] > o2[1]){
                output = 1;
            }else {
            	//끝나는 시간이 같은 케이스에서는 시작시간이 더 빠른 순서로 정렬
                if (o1[0] < o2[0]){	
                    output = -1;
                }else output = 1;
            }
            return output;
        });
        int cnt = 0;
        int nowIndex = 0;
        int endTime = -1;
        while(nowIndex < n){
            if(meetings[nowIndex][0] < endTime){
                nowIndex++;
                continue;
            }
            endTime = meetings[nowIndex][1];
            cnt++;
            nowIndex++;
        }
        System.out.println(cnt);
    }
}

정답참고를 좀 많이해서 풀은 문제