문제
async/await를 사용하면 여러 작업을 시작해 동시에 실행되게 할 수 있습니다. SemaphoreSlim은 보통 한 번에 실행되는 작업 수를 제한합니다.
0부터 n − 1까지 번호가 매겨진 작업들은 durations[i] 시간 단위를 걸립니다. 시간 0에 허용된 한도만큼, 인덱스 순서대로 가능한 많은 작업을 시작하세요. 작업이 끝날 때마다 그것들을 기록하고(같은 순간에 여러 작업이 끝나면 더 작은 인덱스부터), 즉시 인덱스 순서대로 다음 대기 중인 작업을 시작하여 빈 슬롯을 채우세요.
parallel_task_order(durations, limit)를 구현하세요.
Input
durations: 각 작업이 걸리는 시간.
limit: 동시에 실행되는 작업의 최대 개수.
Output
작업이 완료되는 순서대로 task 인덱스를 반환하세요.
제약 조건
1 ≤ n ≤ 100,000
1 ≤ durations[i] ≤ 10^6; 1 ≤ limit ≤ n
예시
입력:
limit = 2
durations = [4, 2, 3, 1]
예상 출력:
expected = [1, 0, 2, 3]입력:
long long limit = 2;
std::vector<long long> durations = {4, 2, 3, 1};
예상 출력:
std::vector<long long> expected = {1, 0, 2, 3};입력:
long limit = 2;
long[] durations = new long[] {4, 2, 3, 1};
예상 출력:
long[] expected = new long[] {1, 0, 2, 3};설명
작업 0과 1이 시작됩니다. 작업 1은 2에 끝나고 작업 2가 시작됩니다(5에 끝남). 작업 0은 4에 끝나고 작업 3이 시작됩니다(5에 끝남). 작업 2와 3은 함께 끝나므로 더 작은 인덱스가 먼저입니다: [1, 0, 2, 3].
입력:
limit = 3
durations = [3, 1, 2]
예상 출력:
expected = [1, 2, 0]입력:
long long limit = 3;
std::vector<long long> durations = {3, 1, 2};
예상 출력:
std::vector<long long> expected = {1, 2, 0};입력:
long limit = 3;
long[] durations = new long[] {3, 1, 2};
예상 출력:
long[] expected = new long[] {1, 2, 0};설명
모든 작업이 한 번에 실행되어 1, 2, 3에 끝납니다: [1, 2, 0].
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
실행 중인 작업을 끝나는 시각, 그다음 번호 순으로 정렬해 두세요.
힌트 2
단계마다 다음 종료 시각으로 건너뛰고 그때 끝나는 작업을 모두 모으세요.
힌트 3
빈 자리는 기다리는 작업으로 번호 순서대로 채우세요.
예상 복잡도
시간 O(n log limit), 추가 공간 O(limit)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.