회의실 하나로 최대한 많이
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
회의실이 하나 있고, 회의 신청이 meetings로 주어집니다. meetings[i] = [start, end]는 i번째 회의가 시각 start에 시작해 시각 end에 끝난다는 뜻입니다.
회의실에서는 한 번에 한 회의만 열 수 있고, 회의는 시작하면 중간에 멈추지 않습니다. 한 회의가 끝나는 시각에 다음 회의를 바로 시작할 수 있습니다. 즉 [1, 3]과 [3, 5]는 둘 다 열 수 있습니다.
신청된 회의 중 일부를 골라 겹치지 않게 열 때, 열 수 있는 회의 수의 최댓값을 반환하세요.
입출력 예
| meetings | result |
|---|---|
[[1, 4], [3, 5], [0, 6], [5, 7], [3, 9], [5, 9], [6, 10], [8, 11], [8, 12], [2, 14], [12, 16]] | 4 |
[[1, 2], [2, 3], [3, 4]] | 3 |
[[0, 10], [1, 2], [3, 4]] | 2 |
입출력 예 설명
예 1 — [1, 4], [5, 7], [8, 11], [12, 16]을 열면 네 회의입니다. 다섯 개를 겹치지 않게 고를 수는 없습니다.
예 2 — 끝나는 시각과 다음 회의의 시작 시각이 같으므로 세 회의를 모두 열 수 있습니다.
예 3 — 긴 회의 [0, 10] 하나 대신 짧은 두 회의를 여는 편이 낫습니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(meetings: int[][]) → int
제한 사항
-
meetings.length meetings[i] = [start, end],startend- 똑같은 회의 신청이 여러 번 있을 수 있습니다.
기대 복잡도
- 시간
- O(N log N)
- 공간
- O(N)
입출력 예
| meetings | 기대 출력 |
|---|---|
[[1,4],[3,5],[0,6],[5,7],[3,9],[5,9],[6,10],[8,11],[8,12],[2,14],[12,16]] | 4 |
[[1,2],[2,3],[3,4]] | 3 |
[[0,10],[1,2],[3,4]] | 2 |
힌트
힌트
첫 회의로 무엇을 고르는 것이 가장 유리할까요? 가장 먼저 끝나는 회의를 고르면 남은 시간이 가장 많이 남습니다. 어떤 최적해든 첫 회의를 "가장 먼저 끝나는 회의"로 바꿔도 여전히 겹치지 않으므로 손해가 없습니다.
그래서 회의를 끝나는 시각 순으로 정렬하고, 앞에서부터 보면서 "직전에 고른 회의가 끝난 뒤에 시작하는가?"만 확인해 고르면 됩니다.
복잡도 목표
회의마다 "이 회의로 끝나는 최대 개수"를 앞선 모든 회의를 보며 계산하는 DP는 이라 효율성 테스트에서 시간 초과가 납니다. 정렬 후 한 번 훑는 이 필요합니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 258 ms | 추정 |
| C++ (GCC, gnu++23) | 258 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1770 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1516 ms | 추정 |
| C# 14 (.NET 10) | 1516 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 11 | 판정만 |
| performance | 60 | 3 | 판정만 |