Lv.2greedysortingsweep-linetwo-pointers
필요한 회의실 개수
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
길이가 같은 두 배열 S와 E가 주어집니다. i번째 회의는 S[i]에 시작하고 E[i]에 끝납니다.
회의는 반열린 구간 동안 회의실 하나를 차지합니다. 한 회의가 끝나는 바로 그 시각에 다른 회의가 시작하면 겹치지 않는 것으로 보아 같은 회의실을 쓸 수 있습니다.
모든 회의를 진행하는 데 필요한 최소 회의실 개수를 반환하세요.
입출력 예
| S | E | result |
|---|---|---|
[0, 5, 15] | [30, 10, 20] | 2 |
[0, 0, 0] | [1, 1, 1] | 3 |
[7] | [10] | 1 |
입출력 예 설명
예 1 — 0~30과 5~10이 겹치고, 15~20도 0~30과 겹칩니다. 동시에 진행되는 회의가 최대 2개이므로 2개면 충분합니다.
예 2 — 세 회의가 같은 시각에 진행되므로 3개가 필요합니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(S: int[], E: int[]) → int
제한 사항
S.length == E.length == N
기대 복잡도
- 시간
- O(N log N)
- 공간
- O(N)
입출력 예
| S | E | 기대 출력 |
|---|---|---|
[0,5,15] | [30,10,20] | 2 |
[0,0,0] | [1,1,1] | 3 |
[7] | [10] | 1 |
힌트
힌트
필요한 개수는 어느 한 시점에 동시에 진행되는 회의의 최대 개수와 같습니다.
시작 시각들과 종료 시각들을 각각 따로 정렬해두고, 시간 순서대로 사건을 처리하세요. 어느 회의가 어느 방에 들어가는지는 알 필요가 없고, "지금 몇 개가 돌고 있나"만 세면 되기 때문에 따로 정렬해도 괜찮습니다.
다음 시작 < 다음 종료 이면 → 방 하나 더 필요 (시작 포인터 전진)
아니면 → 방 하나 비워짐 (종료 포인터 전진)
종료 시각과 시작 시각이 같으면 겹치지 않으므로 부등호는 < 입니다. 두 포인터가 서로 다른 배열을 가리키니, 반복 조건은 시작 포인터가 배열 끝에 닿았는지로 두세요.
복잡도 목표
각 회의마다 다른 모든 회의와 겹치는지 확인하는 풀이는 효율성 테스트에서 시간 초과가 납니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1400 ms | 추정 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1000 ms | 도출됨 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 11 | 판정만 |
| performance | 60 | 4 | 판정만 |