99클럽 코테 스터디 8일차 TIL - 백준 1931 (회의실배정)

그리디 알고리즘

종료 시간을 기준으로 정렬 -> 이전 종료시간에 대해 겹치는 것들은 제외하고 남은 것들 중 선택

빨리 끝나는 것 선택 : a1

a1을 선택한 뒤 다음으로 빨리 끝나는 것 a2 (a1과 겹치므로 제외), a3도 마찬가지

a4는 a1과 겹치지 않으면서 다음으로 빨리 끝남

-> 총 4개 

 

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


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[][] meetingRoom = new int[N][2];
        for(int i=0;i<N;i++){

            StringTokenizer st = new StringTokenizer(br.readLine());
            meetingRoom[i][0] = Integer.parseInt(st.nextToken());
            meetingRoom[i][1]= Integer.parseInt(st.nextToken());
        }

        Arrays.sort(meetingRoom, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[1]==o2[1]){
                    return o1[0]-o2[1];
                }
                return o1[1]-o2[1];
            }
        });
        int count = 0;
        int prev_time= 0;
        for(int i=0;i<N;i++){
            if(prev_time<=meetingRoom[i][0]){
                count++;
                prev_time= meetingRoom[i][1];
            }
        }
        System.out.print(count);
    }


}

 

 

오늘의 회고

• 한 문제를 풀더라도 개념을 정확히 이해하고 풀자...
• 내일(4/9) 학습 예정 : 그리디 알고리즘 공부