[競プロ][Leetcode2589] ジョブ実行時間の最小化

概要

ジョブ実行時間の最小化問題を下記の問題を元に解説する
2589. Minimum Time to Complete All Tasks

問題の要約

無限にジョブを並列実行可能なコンピュータがあるとする。
ある期間の間に実行する必要のあるジョブが複数与えられる。
コンピュータの実行順序を最適化すると最小実行時間はいくつになるか。

考え方

直感ではジョブの実行時間が重なっているほど効率的に計算が可能。
なのでできるだけジョブの実行時間が重なるように実行順序を考える。

1. ジョブの実行優先度はそのジョブの最終実行可能時間で決まる。
   (一番優先度の高いジョブは一番最初に完了させる必要のあるジョブ)
   なのでまずはジョブの最終実行可能時間でソートすることが重要。

2. 実行ジョブを選んだ後はそのジョブをどの時間帯で実行させるかが重要になる。これはそのジョブの実行が遅ければ遅いほど良い。なぜなら遅いほどその次のジョブと実行時間が重なる可能性が高くなるため。

実装

int findMinimumTime(vector<vector<int>>& tasks) {
        sort(tasks.begin(), tasks.end(), [&](auto& t1, auto& t2) {
            if (t1[1] == t2[1]) {
                return t1[0] < t2[0];
            }
            return t1[1] < t2[1];
        });

        int ans = 0;
        vector<bool> executed(tasks.back()[1]+1, false);
        for (auto& task: tasks) {
            // 実行時間
            int remaining_time = task[2];
            // 実行済みの時間があれば実行時間から引く
            for (int i=task[0]; i<=task[1]; i++) {
              if (executed[i]) remaining_time--;
            }
            // 一番遅い実行可能時間から実行していく
            int executing_time = task[1];
            while (remaining_time > 0) {
              if (!executed[executing_time]) {
                executed[executing_time] = true;
                remaining_time--;
                ans++;
              }
              executing_time--;
            }
        }

        return ans;
    }