# Leetcode 2589. Minimum Time to Complete All Tasks
###### tags: `leetcode` `Contest`

[題目連結](https://leetcode.com/problems/minimum-time-to-complete-all-tasks/)

[TOC]

# Concept
對於這種 start, end 區間類型的題目，我們可以很容易聯想到使用sort做排序。
至於要根據start、end哪一個屬性做 sort，我們就必須根據題目定義來做處理。

## A. 根據 Start 做排序
我們可以清楚的知道 做完排序後, 一定會有先後順序關係，
假如我們根據 start 做排序：`tasks[i].start <= tasks[i+1].end`

:::warning
**我們可以很清楚的知道 對於 `tasks[i]` 這區間，**
**一定要選擇最後面的幾個數字，比較有機會與 `tasks[i+1]` 重疊**
:::

> Example: `tasks[i] = {1, 5, 2}`
>
> `tasks[i+1]` 可能會有三種況狀況
> 1. `tasks[i+1] = {6, 8, 2}`
> `tasks[i]` 無論怎麼選，都無法與 `tasks[i+1]` 重疊
>
> 2. `tasks[i+1] = {2, 3, 2}`
> `tasks[i]` 要選擇 `[2, 3]` 才有辦法與 `tasks[i+1]` 重疊
>
> 3. `tasks[i+1] = {4, 5, 2}`
> `tasks[i]` 要選擇 `[4, 5]` 才有辦法與 `tasks[i+1]` 重疊
>
> 從上面的三個例子我們可以看出：
> **這時候會陷入一個困難，選擇數字的範圍 會受到 `tasks[i+1].end` 所影響**

## B. 根據 End 做排序
從上面的例子的結論 我們可以改成從 `end` 來做排序試試看

> 1. `tasks[i] = {1, 5, 2}`，`tasks[i+1] = {6, 8, 2}`
> `tasks[i]` 選擇 `[4, 5]`，`tasks[i+1]` 選擇 `[7, 8]`
> 無論怎麼選都不會互相重疊
>
> 2. `tasks[i] = {2, 3, 2}`，`tasks[i+1] = {1, 5, 2}`
> `tasks[i]` 選擇 `[2, 3]`，`tasks[i+1]` 選擇 `[2, 3]`
>
> 3. `tasks[i] = {1, 5, 2}`，`tasks[i+1] = {4, 5, 2}`
> `tasks[i]` 選擇 `[4, 5]`，`tasks[i+1]` 選擇 `[4, 5]`
> **這邊需要特別小心 `end` 相同時, 需不需要特別考慮 `start`,**
> **從這個例子中看起來是不需要特別考慮的**

## C. 判斷重複出現過的數字
最後由於題目數據範圍是
* `1 <= tasks.length <= 2000`
* `1 <= start_i, end_i <= 2000`

因此我們對於使用過的數字使用 vector 來記錄哪些數字前面所使用過，對於每一個尋訪到的task，先把計算範圍內有哪些數字使用過，最後再從 `end -> start`，一個一個補上即可。

## 完整程式碼
`TC: O(NlogN)` `SC: O(N)`

class Solution {
public:
    static bool cmp(vector<int> &a, vector<int> &b) {
        return a[1] < b[1];
    }
    int findMinimumTime(vector<vector<int>>& tasks) {
        int n = tasks.size();
        int output = 0;
        vector<bool> visited(2001, false);
        sort(tasks.begin(), tasks.end(), cmp);
        
        for(int i = 0 ; i < n ; i++) {
            int start = tasks[i][0];
            int end = tasks[i][1];
            int count = tasks[i][2];
            int owner = 0;
            for(int j = start ; j <= end ; j++) {
                owner += visited[j];
            }
            if(owner >= count) {
                continue;
            }
            for(int j = end ; (j >= start) && (owner < count) ; j--) {
                if(visited[j] == false) {
                    owner++;
                    visited[j] = true;
                    output++;
                }
            }
        }
        return output;
    }
};

{%hackmd hjePmt98S8a_uls4-6_hNg %}