import sys
import heapq
input = sys.stdin.readline
n = int(input())
arr = []
for _ in range(n):
arr.append(list(map(int, input().split())))
arr.sort()
queue = []
heapq.heappush(queue, arr[0][1])
for i in range(1, n):
if not queue:
heapq.heappush(queue, arr[i][1])
else:
if queue[0] <= arr[i][0]:
heapq.heappop(queue)
heapq.heappush(queue, arr[i][1])
else:
heapq.heappush(queue, arr[i][1])
print(len(queue))
나의 풀이 (Java)
import java.util.*;
public class Main {
static class Lesson implements Comparable<Lesson> {
private final int start;
private final int end;
public Lesson(int start, int end) {
this.start = start;
this.end = end;
}
public int compareTo(Lesson compare) {
if (this.start == compare.start) {
return this.end - compare.end;
}
return this.start - compare.start;
}
}
public int solution(List<Lesson> lessons) {
Collections.sort(lessons);
PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.add(lessons.get(0).end);
for (int i = 1; i < lessons.size(); i++) {
if (queue.isEmpty()) {
queue.add(lessons.get(i).end);
}
else {
if (queue.peek() <= lessons.get(i).start) {
queue.poll();
queue.add(lessons.get(i).end);
}
else {
queue.add(lessons.get(i).end);
}
}
}
return queue.size();
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
List<Lesson> lessons = new ArrayList<>();
for (int i = 0; i < N; i++) {
int start = sc.nextInt();
int end = sc.nextInt();
lessons.add(new Lesson(start, end));
}
Main main = new Main();
System.out.println(main.solution(lessons));
}
}
코드 설명 및 풀이법
시간제한이 1초이기 때문에 O(n^2)의 시간복잡도로는 시간초과가 뜬다.
큐를 사용해서 문제를 해결할 수 있다.
우선, 시작으로 맨 첫 강의가 끝나는 시간을 큐에 넣어준다.
그 후, 강의를 하나씩 돌면서 현재 큐에 있는 시간과 강의 시작 시간을 비교해서 시작 시간이 끝나는 시간보다 크거나 같다면, 강의장을 추가할 필요가 없는 것이므로 기존에 들어있던 값을 pop해주고, 새 강의의 끝나는 시각을 업데이트 해준다.
만약 다음에 들어오는 강의의 시작시간이 현재 큐에 있는 강의 종료 시각보다 작다면, 새로운 강의장이 필요하다는 의미이므로 그대로 해당 강의의 끝나는 시각을 추가해주면 된다.