<Algorithm> 39. 1931번 회의실

1. 1931번 회의실

• 최적의 경우를 이용하는 그디리 알고리즘 문제, 끝나는 시간을 판단하여 회의실을 배정 해야한다.

• 주의할점은 정렬을 두번 해주어야 한다. 끝나는 시간이 같은데 더 느린 경우가 생길 수 있기 때문이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        ArrayList<Time> aList = new ArrayList<>();
        
        for(int i = 0; i < N; i ++) {
            st = new StringTokenizer(br.readLine());
            aList.add(new Time(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }
        
        Collections.sort(aList,new Comparator<Time>() {
            @Override
            public int compare(Time o1, Time o2) {
                if(o1.end == o2.end) {
                    return o1.start - o2.start;
                }
                return o1.end - o2.end;
            } // 뒤에꺼 정렬 (같으면 앞에꺼 내림차 정렬)
        });
        
        int endTime = aList.get(0).end;
        int count = 1;
 
        for(int i = 1 ; i < N ; i++) {
            if(endTime <= aList.get(i).start){
                endTime = aList.get(i).end;
                count++;
            }
        }
        
        System.out.println(count);
    }
}
 
class Time{
    int start;
    int end;
    public Time(int start, int end) {
        this.start = start;
        this.end = end;
    }
    
}