[softeer/java] 강의실배정 / Scanner보다는 BufferedReader 사용하기

1. 문제

김교수는 강의실 1개에 최대한 많은 강의를 배정하려고 한다. 배정된 강의는 서로 겹치지 않아야 하며 수업시간의 길이와 상관없이 최대한 강의를 많이 배정하라. 단, 두 강의의 시작시간과 종료시간은 겹쳐도 된다. 

[제약조건]

1 ≤ N ≤ 106 인 정수
1 ≤ Si ＜ Fi ≤ 109

[입력형식]

첫 번째 줄에 강의 개수 N이 주어진다. i + 1 (1 ≤ i ≤ N)번째 줄에는 i번째 강의의 시작 시간 Si와 종료 시간 Fi가 주어진다.

[출력형식]

첫 번째 줄에 최대 강의 수를 출력하라.

[입력예제1]

3
1 3
2 4
3 5

[출력예제1]

2

 

2. 풀이방법

- 이 문제는 greedy 알고리즘을 사용한 문제로, 정렬만 잘 하면 된다.

- end 타임을 기준으로 오름차순 정렬을 해준다.

- 단계 2의 

3.  정답

- scanner를 사용해서 입력값을 받았는데  시간제한 초과가 나왔다.

- BufferedReader를 사용해서 입력값을 받아주자.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Room implements Comparable<Room>{
    public int start;
    public int end;

    public Room(int start, int end) {
        this.start = start;
        this.end = end;
    }
    @Override
    public int compareTo(Room r) {
        if (r.end == this.end) {
            return this.start - r.start;
        }
        return this.end - r.end;
    }

}

public class Main {
    public static void main(String[] args) throws IOException {
    	//BufferedReader 사용하기
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());

        List<Room> lists = new ArrayList<>();
        for (int i=0; i<n; i++) {
            String[] tmp = reader.readLine().split(" ");
           lists.add(new Room(Integer.parseInt(tmp[0]), Integer.parseInt(tmp[1])));
        }
        //오름차순 정렬
        Collections.sort(lists);
        
       
        int end = Integer.MIN_VALUE;
        int answer = 0;
        for (int i=0; i<lists.size(); i++) {
            if (end <= lists.get(i).start) {
                end = lists.get(i).end;
                answer++;
            }
        }
        System.out.println(answer);
    }
}​

 

좌 : Scanner 사용 / 우 : BufferedReader 사용