문제

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

N개의 강의가 있다. 우리는 모든 강의의 시작하는 시간과 끝나는 시간을 알고 있다. 이때, 우리는 최대한 적은 수의 강의실을 사용하여 모든 강의가 이루어지게 하고 싶다.

물론, 한 강의실에서는 동시에 2개 이상의 강의를 진행할 수 없고, 한 강의의 종료시간과 다른 강의의 시작시간이 겹치는 것은 상관없다. 필요한 최소 강의실의 수를 출력하는 프로그램을 작성하시오.

---

입력

첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 번호는 1부터 N까지 붙어 있으며, 입력에서 꼭 순서대로 주어지지 않을 수 있으나 한 번씩만 주어진다. 강의 시작 시간과 강의 종료 시간은 0 이상 10억 이하의 정수이고, 시작 시간은 종료 시간보다 작다.

---

출력

첫째 줄에 필요한 최소 강의실 개수를 출력한다.

---

풀이

접근방법

시간제한 2초, 메모리 128MB이다.

그리디의 대표 문제이다.
예제를 기준으로 생각을 해본다.

- 예제 입력
8
6 15 21
7 20 25
1 3 8
3 2 14
8 6 27
2 7 13
4 12 18
5 6 20

우선 입력들을 정렬을 해보자.

1. 시작시간을 빠른 순서로
2. 시작시간이 같다면, 빨리 끝나는 순서로.

강의번호	시작시간	종료시간
3	2	14
1	3	8
5	6	20
8	6	27
2	7	13
4	12	18
6	15	21
7	20	25

이제 다시 살펴보자.
3번 강의가 2에 시작하여 14에 종료된다.
따라서 3번 강의에 1번 강의실을 배정한다고 해보자.
현재 강의실 사용 현황은 아래와 같다

강의실 번호	강의번호	시작시간	종료시간
1	3	2	14

1번 강의는 3에 시작해서 8에 끝나기때문에 1번 강의실을 사용할 수 없다.
따라서 새로운 강의실을 배정해야 한다.

강의실 번호	강의번호	시작시간	종료시간
1	3	2	14
2	1	3	8

마찬가지로 쭉 진행을 해본다.

강의실 번호	강의번호	시작시간	종료시간
1	3	2	14
2	1	3	8
3	5	6	20
4	8	6	27
5	2	7	13

이제 4번 강의를 진행하기 위해 살펴보자.
4번 강의는 12에서 시작하여 18에 종료된다.
4번 강의가 시작할시간인 12에는 2번 강의실의 사용이 종료되기 때문에,
새로운 강의실이 아니라 2번 강의실에서 이어서 진행 할 수 있다.

강의실 번호	강의번호	시작시간	종료시간
1	3	2	14
2	4	12	18
3	5	6	20
4	8	6	27
5	2	7	13

이런식으로 현재 배정된 강의실의 종료시간을 쫓아가며 최대 몇개의 강의실이 필요한지 찾을 수 있다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;

public class Main {
	static int N;

	static class Lecture implements Comparable<Lecture> {
		int no;
		int start;
		int end;

		Lecture(String[] str) {
			no = stoi(str[0]);
			start = stoi(str[1]);
			end = stoi(str[2]);
		}

		public int compareTo(Lecture o) {
			if (this.start == o.start)
				return this.end - o.end;
			return this.start - o.start;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		N = stoi(in.readLine());
		Lecture[] list = new Lecture[N];

		for (int i = 0; i < N; ++i)
			list[i] = new Lecture(in.readLine().split(" "));

		Arrays.sort(list);

		PriorityQueue<Integer> pq = new PriorityQueue<>();
		for (int i = 0; i < N; ++i) {
			if (pq.isEmpty()) {
				pq.add(list[i].end);
			} else {
				int endTime = pq.peek();
				if (list[i].start < endTime) {
					pq.add(list[i].end);
				} else {
					pq.poll();
					pq.add(list[i].end);
				}
			}
		}
		System.out.println(pq.size());
	}

	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}