[알고리즘] 그리디 알고리즘 : 회의실 배정 1931

[문제] 

https://www.acmicpc.net/problem/1931

 

[회고] 

• 처음에는 소요 시간이 적은 미팅을 먼저 배정해야 한다고 생각. 그러나 회의가 끝나는 시간을 기준으로 정렬해야 하는 문제였음.
• 알고리즘 분류에 ‘그리디 알고리즘’, ‘정렬’이라고 적힌 것을 힌트 삼아 생각할 것.
• 잘한 점은 'input.txt.'를 만들어서 copy&paste 시간을 줄인 것. 

💡 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다.

• 100,000은 for문 안에 for문을 쓸 수 없다. + Order(NlogN)은 쓸 수 있다. = Arrays.sort()를 사용할 것.

💡 [힌트] (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

• 힌트를 잘 읽어 보면 ‘회의가 끝나는 시간’을 기준으로 한 것을 유추할 수 있다.

 

[코드] 

package org.example.basic.ch03;

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class GreedyPractice4 {
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("input.txt"));

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int theNumberOfMeeting = Integer.parseInt(br.readLine());
        int[][] arrayOfMeeting = new int[theNumberOfMeeting][2];

        for (int i = 0; i < theNumberOfMeeting; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine()); // 1 4
            arrayOfMeeting[i][0] = Integer.parseInt(st.nextToken());
            arrayOfMeeting[i][1] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arrayOfMeeting, (a, b) -> a[1] == b[1] ? a[0] - b[0] : a[1] - b[1]);

        int count = 0;
        int endTime = 0;

        for (int i = 0; i < theNumberOfMeeting; i++) {
            if (arrayOfMeeting[i][0] >= endTime) {
                endTime = arrayOfMeeting[i][1];
                count++;
            }
        }
        System.out.println(count);
    }
}