[BOJ/SilverI] 1931. 회의실 배정 - JAVA 자바

1931번: 회의실 배정

• 504ms
• 그리디

한 개의 회의실을 사용할 수 있는 회의의 최대 개수를 구하는 문제로 그리디 알고리즘의 대표적인 문제이다.

 

# 접근 방식

1. 일찍 끝나야 다음 회의를 진행하므로 끝나는 시간을 기준으로 오름차순 정렬한다.

2. 회의 끝나는 시간이 다음 회의 시작 시간보다 작거나 같아야한다.

 

Comparable 인터페이스를 통해 끝나는 시간을 기준으로 오름차순 정렬하며 끝나는 시간이 같을 때는 시작 시간 기준으로 오름차순 정렬을 해준다.

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

public class Main {

    static class Node implements Comparable<Node> {
        int startT;
        int endT;
        public Node(int startT, int endT) {
            this.startT = startT;
            this.endT = endT;
        }
        @Override
        public int compareTo(Node o) {
            if(this.endT == o.endT)
                return this.startT - o.startT;
            return this.endT - o.endT;
        }        
    }

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

        int n = Integer.parseInt(br.readLine());
        List<Node> list = new ArrayList<Main.Node>();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            list.add(new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        Collections.sort(list);

        int endTime = 0;
        int result = 0;
        for(Node node : list) {
            if(endTime <= node.startT) {
                result++;
                endTime = node.endT;
            }
        }
        System.out.println(result);

    }
}