[그리디, DP] 백준 1931. 회의실 배정

회의시간을 모두 비교하면서 O(n)의 시간으로 진행할 수 있는 방법에 대해 고민함

• 회의의 최대 수는 10만이므로, 하나씩 다 비교한다면 O(n!)으로 시간 무조건 초과

과정

1. 입력 예제를 그려봤을 때, 나열하고 비교하는 순서를 시작 시간이 가장 빠른 순으로 해야겠다고 생각함.
2. 시작 시간이 같을 경우에는 더 빨리 끝나는 회의를 우선 순위로 둠.

-> 나열 후 하나씩 큐에 삽입하면서, 마지막 회의가 추가로 진행할 회의보다 빨리 끝나면 그대로 큐에 넣고,
추가로 진행할 회의가 마지막 회의보다 더 빨리 시작하고, 더 빨리 끝나면 마지막회의를 삭제한 후 회의를 추가하기.

import java.util.*;
import java.io.*;

public class Main {
    static class Meeting implements Comparable<Meeting>{
        int hour;
        int start;
        int end;

        @Override
        public int compareTo(Meeting m1){
            if(this.start < m1.start){
                return -1;
            }else if(this.start > m1.start){
                return 1;
            }else{
                return this.end - m1.end;
            }
        }

        Meeting (int start, int end){
            this.start = start;
            this.end = end;
            this.hour = end - start;
        }

    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 배달할 설탕의 무게 (kg)
        int n = Integer.parseInt(st.nextToken());
        int start, end;

        Meeting[] meetings = new Meeting[n];

        for(int i = 0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            start = Integer.parseInt(st.nextToken());
            end = Integer.parseInt(st.nextToken());

            meetings[i] = new Meeting(start, end);
        }

        Arrays.sort(meetings);


        Deque<Meeting> meetingList = new LinkedList<>();
        for(int i = 0; i<n; i++){
            //System.out.println(meetings[i].start + ", " + meetings[i].end + ", " + meetings[i].hour);

            if(meetingList.isEmpty()){
                meetingList.add(meetings[i]);
            }

            else{
                Meeting currMeeting = meetingList.getLast();

                if (meetings[i].start < currMeeting.end) {
                    if(meetings[i].end < currMeeting.end){
                        meetingList.removeLast();
                        meetingList.addLast(meetings[i]);
                    }
                }else{
                    meetingList.addLast(meetings[i]);
                }
            }
        }

        System.out.println(meetingList.size());
    }
}