Funcia
Lv.1greedysorting

회의실 하나로 최대한 많이

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

회의실이 하나 있고, 회의 신청이 meetings로 주어집니다. meetings[i] = [start, end]는 i번째 회의가 시각 start에 시작해 시각 end에 끝난다는 뜻입니다.

회의실에서는 한 번에 한 회의만 열 수 있고, 회의는 시작하면 중간에 멈추지 않습니다. 한 회의가 끝나는 시각에 다음 회의를 바로 시작할 수 있습니다. 즉 [1, 3]과 [3, 5]는 둘 다 열 수 있습니다.

신청된 회의 중 일부를 골라 겹치지 않게 열 때, 열 수 있는 회의 수의 최댓값을 반환하세요.

입출력 예

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

제한 사항

  • 1≤1 \le meetings.length ≤200,000\le 200{,}000
  • meetings[i] = [start, end], 0≤0 \le start << end ≤109\le 10^9
  • 똑같은 회의 신청이 여러 번 있을 수 있습니다.

기대 복잡도

시간
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는 O(N2)O(N^2)이라 효율성 테스트에서 시간 초과가 납니다. 정렬 후 한 번 훑는 O(Nlog⁡N)O(N \log N)이 필요합니다.

언어별 시간 제한

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

테스트 그룹

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

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