Funcia
Lv.3greedyheapsorting

마감 전에 끝낼 일 고르기

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

일 n개가 있습니다. i번 일은 하루가 걸리고, **deadlines[i]일째 이전(그날 포함)**에 끝내면 보수 profits[i]를 받습니다. 하루에 일 하나만 할 수 있고, 1일째부터 일을 시작합니다. 마감을 넘긴 일은 하지 않습니다.

받을 수 있는 보수 합의 최댓값을 반환하세요.

입출력 예

deadlinesprofitsresult
[2, 1, 2, 1, 3][100, 19, 27, 25, 15]142
[1, 1, 1][5, 9, 2]9
[1000000000][7]7

입출력 예 설명

예 1 — 1일째 보수 27(마감 2), 2일째 100(마감 2), 3일째 15(마감 3)를 하면 142입니다.

예 2 — 마감이 모두 1일째라 하나만 할 수 있습니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(deadlines: int[], profits: int[]) → long

제한 사항

  • 1≤n=1 \le n = deadlines.length == profits.length ≤200,000\le 200{,}000
  • 1≤1 \le deadlines[i] ≤109\le 10^9, 1≤1 \le profits[i] ≤109\le 10^9
  • 답은 32비트 정수를 넘을 수 있습니다.

기대 복잡도

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

입출력 예

deadlinesprofits기대 출력
[2,1,2,1,3][100,19,27,25,15]142
[1,1,1][5,9,2]9
[1000000000][7]7

힌트

힌트

일을 마감이 빠른 순으로 보면서, "지금까지 하기로 한 일들"을 보수 기준 최소 힙에 담으세요.

  • 일을 일단 힙에 넣습니다.
  • 힙의 크기(하기로 한 일의 수)가 지금 일의 마감보다 커지면, 마감 안에 다 할 수 없다는 뜻이니 보수가 가장 작은 일을 하나 뺍니다.

마지막에 힙에 남은 보수의 합이 답입니다. 마감 순으로 보기 때문에, 크기 k인 집합은 항상 1..k일에 순서대로 배치할 수 있습니다.

마감이 10910^9까지라 날짜 배열을 만들 수 없다는 점도 이 방법이 편한 이유입니다.

복잡도 목표

보수가 큰 일부터 "마감 이전의 비어 있는 가장 늦은 날"을 한 칸씩 찾아 내려가는 방식은 O(N2)O(N^2)이라 효율성 테스트에서 시간 초과가 납니다.

언어별 시간 제한

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

테스트 그룹

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

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