問題
async/await を使うと、複数のタスクを開始して同時に実行させることができます。SemaphoreSlim は同時実行数の上限を制御するのによく使われます。
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.
parallel_task_order(durations, limit) を実装してください。
入力
durations: 各タスクにかかる時間。
limit: 同時に実行できるタスクの最大数。
出力
完了した順にタスクのインデックスを返してください。
制約
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 つずつ開いてみましょう。
ヒント 1
実行中のタスクを終了時刻、次に番号の順で並べておきます。
ヒント 2
各ステップで次の終了時刻に進み、そのとき終わるタスクをすべて集めます。
ヒント 3
空いた枠を、待っているタスクで番号順に埋めます。
目安の計算量
時間 O(n log limit)、追加メモリ O(limit)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。