1931 회의실 배정 (JAVA)

• 빨리 끝나는 회의부터 탐색하여 가장 많은 회의의 경우의 수를 찾아내는 그리디 알고리즘 기초 문제.
• 주의할점은, 시작하자 마자 끝나는 회의가 있기 때문에 종료시간이 같다면 시작시간을 오름차순 정렬해주어야 한다.

• (21,21) (18,21) (17,21) 의 순서로 회의를 탐색한다면, 가능한 회의는 단 하나뿐이지만

• (17,21) (18,21) (21,21) 의 순서로 회의를 탐색하면 가능한 회의의 수가 두개 이기 때문이다.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

/* 1931 회의실 배정 */
public class Main {
    static class Lect implements Comparable<Lect>{
        public int start;
        public int end;
        public Lect(int start, int end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public int compareTo(Lect o) {
            if(this.end == o.end)	// 종료시간이 같다면, 시작시간을 기준으로 오름차순 정렬
                return this.start - o.start;
            else
                return this.end - o.end;
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ArrayList<Lect> list = new ArrayList<>();
        
        for(int i=0; i<n; ++i)
            list.add(new Lect(sc.nextInt(), sc.nextInt()));

        Collections.sort(list);
        
        int count = 0;
        int min = Integer.MIN_VALUE;
        
        for(Lect l : list){
            if(l.start >= min){
                count++;
                min = l.end;
            }
        }
        System.out.println(count);
    }
}