[JAVA] 백준 1931- 회의실 배정

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

1931번: 회의실 배정

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

class Time implements Comparable<Time>{

    public int start, end;

    public Time(int start, int end) {
        this.start = start;
        this.end = end;
    }
    @Override
    public int compareTo(Time o) {
        if(this.end == o.end) return this.start - o.start; // 끝나는 시간이 같으면 시작 시간 오름차순
        return this.end - o.end; // 끝나는 시간 오름차순
    }
}
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());

        ArrayList<Time> list = new ArrayList<>();

        StringTokenizer st;
        while(n-->0){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            list.add(new Time(start, end));
        }
        Collections.sort(list);

        int meetingEnd = 0;
        int cnt = 0;

        for(Time t : list){
            if(t.start >= meetingEnd){ // 직전에 끝났던 회의 시간보다 그 다음 회의 시작 시간이 같거나 크면
                cnt++;
                meetingEnd = t.end; // 직전에 끝났던 회의 시간 갱신
            }
        }
        System.out.println(cnt);
    }
}

 

 

 

1.최대한 많은 회의를 배치하려면 회의의 종료 시간이 빨라야 한다. 

 

시작 하는 시간이 빨라도 늦게 끝나면 최대 가능한 회의를 만들 수 없기 때문에 각각의 스케줄에서 회의의 종료 시간이 중요하다. 

따라서 회의의 종료 시간에 따라 오름차순 정렬을 한다. 

 

 

2.이전 회의의 종료 시간과 이후 회의의 시작 시간이 겹치면 안된다.(같을 수는 있다) 

 

이전 회의의 종료 시간보다 다음 회의의 시작 시간이 같거나 크면 카운팅을 하고, 다음 회의의 종료 시간을 갱신한다.