Leetcode 2589. Minimum Time to Complete All Tasks

[Woodyiiiiiii]

这道题首先就是贪心思想。尽量使用交接处密度更高的位置。

先将intervals按照末端从小到大排序，然后从末端开始，以O(n^2)的时间复杂度进行遍历，并创建大小为2000的访问数组。这样可以保证每个intervals的空间都最大利用。

难点是如何想到要按照末端排序的，而不是前端。其实就是贪心思想，相交更多的部分显然是末端开始。

class Solution {
    public int findMinimumTime(int[][] tasks) {
        Arrays.sort(tasks, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0]);
        int ans = 0;
        boolean[] done = new boolean[2001];
        for (int i = 0; i < tasks.length; ++i) {
            if (tasks[i][2] <= 0) {
                continue;
            }
            for (int k = tasks[i][1]; k >= tasks[i][0] && tasks[i][2] > 0; --k) {
                if (done[k]) {
                    continue;
                }
                done[k] = true;
                for (int j = i; j < tasks.length; ++j) {
                    if (k >= tasks[j][0] && k <= tasks[j][1] && tasks[j][2] > 0) {
                        tasks[j][2]--;
                    }
                }
                ans++;
            }
        }
        return ans;
    }
}

还可以用树状数组/线段树。

---

• 2589. Minimum Time to Complete All Tasks