문제 링크
문제
티어: 골드 3
알고리즘: 그리디, 정렬
N개의 강의가 있다. 우리는 모든 강의의 시작하는 시간과 끝나는 시간을 알고 있다. 이때, 우리는 최대한 적은 수의 강의실을 사용하여 모든 강의가 이루어지게 하고 싶다.
물론, 한 강의실에서는 동시에 2개 이상의 강의를 진행할 수 없고, 한 강의의 종료시간과 다른 강의의 시작시간이 겹치는 것은 상관없다. 필요한 최소 강의실 수 K와, 각 강의마다 강의실을 배정하는 프로그램을 작성하시오.
입력
첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 번호는 1부터 N까지 붙어 있으며, 입력에서 꼭 순서대로 주어지지 않을 수 있으나 한 번씩만 주어진다. 강의 시작 시간과 강의 종료 시간은 0 이상 10억 이하의 정수이고, 시작 시간은 종료 시간보다 작다.
출력
첫째 줄에 필요한 최소 강의실 개수 K를 출력한다. 둘째 줄부터 N개의 줄에 걸쳐 각 강의에 배정할 강의실 번호를 순서대로 출력한다. 편의상 강의실 번호는 1, 2, ..., K 로 매긴다.
풀이
최대한 적은 수의 강의실을 사용해서 모든 강의를 이루어지게 해야 한다
그러면 강의가 종료 시점에서 시작할 수 있는 강의 중 가장 빠르게 시작하는 강의를 듣는 것이 최선이다.
그러면 강의마다 모든 강의를 순차 탐색으로 찾는 방법을 생각할 수 있지만, N이 최대 10만이기 때문에 시간 초과가 발생한다.
O(N) 풀이를 생각해야 하는데, 그 풀이는 다음과 같다.
먼저, 종료 시점을 기준으로 오름차순 정렬하고, 시작 시점 또한 오름차순으로 정렬한다.
종료 시점을 순차적으로 돌면서, 시작 시점을 순차적으로 탐색한다.
종료 시점 강의 다음 시작 시점 강의를 배정할 수 없다면, 당연히 그 이후 종료 시점 강의도 배정할 수 없다.(종료 시점이 오름차순으로 정렬되어 있기 때문에)
그래서 새 강의실을 배정해 주고, 시작 시점 강의에서 배정할 수 있는 강의가 있다면, 그 이후 시작 시점 강의들도 다 배정해 줄 수 있다.(시작 시점이 오름차순으로 정렬되어 있기 때문에)
그러면 그 강의들 중에 어떤 강의를 배정해 주는 것이 최선의 선택일까? 가장 빠르게 시작하는 강의를 선택하는 것이 최선이다. 왜냐하면 다음 종료 시점 강의는 현재 종료 시점 강의보다 end가 더 크기 때문에, start가 빠른 강의를 최대한 앞에서 배정해야 한다. 그래서 최초로 배정할 수 있는 시작 시점 강의를 선택하는 것이다.
그래서 그리디, 정렬을 사용한 풀이는 O(N)으로 시간 초과 없이 풀 수 있다.
소스 코드
import java.io.*;
import java.util.*;
class Lecture {
int num, roomNum, start, end;
Lecture(int num, int start, int end) {
this.num = num;
this.roomNum = -1;
this.start = start;
this.end = end;
}
public void setRoomNum(int roomNum) {
this.roomNum = roomNum;
}
public int getRoomNum() {
return this.roomNum;
}
}
public class Main {
static int N;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
Lecture[] lectures = new Lecture[N];
for(int i=0; i<N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int num = Integer.parseInt(st.nextToken());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
lectures[i] = new Lecture(num, start, end);
}
Arrays.sort(lectures, new Comparator<Lecture>() {
@Override
public int compare(Lecture l1, Lecture l2) {
return Integer.compare(l1.num, l2.num);
}
});
StringBuilder sb = new StringBuilder();
sb.append(assignRoomNum(lectures)).append('\n');
for(int i=0; i<N; i++) {
sb.append(lectures[i].getRoomNum()).append('\n');
}
System.out.println(sb.toString().trim());
}
static int assignRoomNum(Lecture[] lectures) {
ArrayList<Lecture> sList = new ArrayList<>();
ArrayList<Lecture> eList = new ArrayList<>();
for(int i=0; i<lectures.length; i++) {
sList.add(lectures[i]);
eList.add(lectures[i]);
}
Collections.sort(sList, new Comparator<Lecture>() {
@Override
public int compare(Lecture l1, Lecture l2) {
return Integer.compare(l1.start, l2.start);
}
});
Collections.sort(eList, new Comparator<Lecture>() {
@Override
public int compare(Lecture l1, Lecture l2) {
return Integer.compare(l1.end, l2.end);
}
});
int k = 1; //새로 배정할 강의실 번호
int sp = 0;
for(int i=0; i<eList.size(); i++) {
if(sp == sList.size()) {
break;
}
while(sp < sList.size()) {
if(eList.get(i).end > sList.get(sp).start) {
sList.get(sp).setRoomNum(k);
k += 1;
sp += 1;
} else {
sList.get(sp).setRoomNum(eList.get(i).getRoomNum());
sp += 1;
break;
}
}
}
return k -= 1;
}
}