Funcia
Lv.2greedysortingsweep-linetwo-pointers

필요한 회의실 개수

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

길이가 같은 두 배열 S와 E가 주어집니다. i번째 회의는 S[i]에 시작하고 E[i]에 끝납니다.

회의는 반열린 구간 [S[i], E[i])[S[i],\ E[i]) 동안 회의실 하나를 차지합니다. 한 회의가 끝나는 바로 그 시각에 다른 회의가 시작하면 겹치지 않는 것으로 보아 같은 회의실을 쓸 수 있습니다.

모든 회의를 진행하는 데 필요한 최소 회의실 개수를 반환하세요.

입출력 예

SEresult
[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

제한 사항

  • 1≤N≤200,0001 \le N \le 200{,}000
  • S.length == E.length == N
  • 0≤S[i]<E[i]≤1090 \le S[i] < E[i] \le 10^9

기대 복잡도

시간
O(N log N)
공간
O(N)

입출력 예

SE기대 출력
[0,5,15][30,10,20]2
[0,0,0][1,1,1]3
[7][10]1

힌트

힌트

필요한 개수는 어느 한 시점에 동시에 진행되는 회의의 최대 개수와 같습니다.

시작 시각들과 종료 시각들을 각각 따로 정렬해두고, 시간 순서대로 사건을 처리하세요. 어느 회의가 어느 방에 들어가는지는 알 필요가 없고, "지금 몇 개가 돌고 있나"만 세면 되기 때문에 따로 정렬해도 괜찮습니다.

다음 시작 < 다음 종료 이면  → 방 하나 더 필요 (시작 포인터 전진)
아니면                     → 방 하나 비워짐 (종료 포인터 전진)

종료 시각과 시작 시각이 같으면 겹치지 않으므로 부등호는 < 입니다. 두 포인터가 서로 다른 배열을 가리키니, 반복 조건은 시작 포인터가 배열 끝에 닿았는지로 두세요.

복잡도 목표

각 회의마다 다른 모든 회의와 겹치는지 확인하는 O(N2)O(N^2) 풀이는 효율성 테스트에서 시간 초과가 납니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251400 ms추정
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1000 ms도출됨

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4011판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.