문제
With async/await you can start several tasks and let them run at the same time. A SemaphoreSlim often caps how many run at once.
Tasks numbered 0 to n − 1 take durations[i] time units. At time 0 start as many tasks as the limit allows, in index order. Whenever tasks finish, record them (if several finish at the same moment, lower index first) and immediately start the next waiting tasks, in index order, to fill the free slots.
Implement parallel_task_order(durations, limit).
Input
durations: How long each task takes.
limit: The maximum number of tasks running at the same time.
Output
Return the task indices in the order they finish.
제약 조건
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};설명
Tasks 0 and 1 start. Task 1 ends at 2 and task 2 starts (ends at 5). Task 0 ends at 4 and task 3 starts (ends at 5). Tasks 2 and 3 finish together, lower index first: [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};설명
All tasks run at once and finish at 1, 2 and 3: [1, 2, 0].
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
Keep the running tasks ordered by finish time, then by index.
힌트 2
Each step jumps to the next finish time and collects every task ending then.
힌트 3
Refill free slots with the next waiting tasks in index order.
예상 복잡도
O(n log limit) time, O(limit) extra space
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.