Problem

There is a computer that can run an unlimited number of tasks at the same time. You are given a 2D integer array tasks where tasks[i] = [starti, endi, durationi] indicates that the ith task should run for a total of durationi seconds (not necessarily continuous) within the inclusive time range [starti, endi].

You may turn on the computer only when it needs to run a task. You can also turn it off if it is idle.

Return the minimum time during which the computer should be turned on to complete all tasks.

Examples

Example 1

1
2
3
4
5
6
7

Input: tasks = [[2,3,1],[4,5,1],[1,5,2]]
Output: 2
Explanation: 
- The first task can be run in the inclusive time range [2, 2].
- The second task can be run in the inclusive time range [5, 5].
- The third task can be run in the two inclusive time ranges [2, 2] and [5, 5].
The computer will be on for a total of 2 seconds.

Example 2

1
2
3
4
5
6
7

Input: tasks = [[1,3,2],[2,5,3],[5,6,2]]
Output: 4
Explanation: 
- The first task can be run in the inclusive time range [2, 3].
- The second task can be run in the inclusive time ranges [2, 3] and [5, 5].
- The third task can be run in the two inclusive time range [5, 6].
The computer will be on for a total of 4 seconds.

Constraints

  • 1 <= tasks.length <= 2000
  • tasks[i].length == 3
  • 1 <= starti, endi <= 2000
  • 1 <= durationi <= endi - starti + 1

Solution

Method 1 – Greedy with Reverse Scheduling

Intuition

To minimize the computer’s on-time, we schedule tasks as late as possible within their allowed intervals. By processing tasks in order of their end times, we can greedily fill the latest available slots, ensuring overlap and minimizing total on-time.

Approach

  1. Sort tasks by their end time.
  2. For each task, count how many seconds in its interval are already scheduled (computer on).
  3. If more time is needed, schedule the remaining seconds at the latest possible times in the interval.
  4. Use a set or array to track which seconds are scheduled.
  5. Return the total number of scheduled seconds.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int findMinimumTime(vector<vector<int>>& tasks) {
        sort(tasks.begin(), tasks.end(), [](auto &a, auto &b) { return a[1] < b[1]; });
        vector<bool> on(2001, false);
        int ans = 0;
        for (auto &t : tasks) {
            int cnt = 0;
            for (int i = t[0]; i <= t[1]; ++i) cnt += on[i];
            int need = t[2] - cnt;
            for (int i = t[1]; need > 0 && i >= t[0]; --i) {
                if (!on[i]) { on[i] = true; ans++; need--; }
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func findMinimumTime(tasks [][]int) int {
    sort.Slice(tasks, func(i, j int) bool { return tasks[i][1] < tasks[j][1] })
    on := make([]bool, 2001)
    ans := 0
    for _, t := range tasks {
        cnt := 0
        for i := t[0]; i <= t[1]; i++ {
            if on[i] { cnt++ }
        }
        need := t[2] - cnt
        for i := t[1]; need > 0 && i >= t[0]; i-- {
            if !on[i] { on[i] = true; ans++; need-- }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int findMinimumTime(int[][] tasks) {
        Arrays.sort(tasks, Comparator.comparingInt(a -> a[1]));
        boolean[] on = new boolean[2001];
        int ans = 0;
        for (int[] t : tasks) {
            int cnt = 0;
            for (int i = t[0]; i <= t[1]; i++) if (on[i]) cnt++;
            int need = t[2] - cnt;
            for (int i = t[1]; need > 0 && i >= t[0]; i--) {
                if (!on[i]) { on[i] = true; ans++; need--; }
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun findMinimumTime(tasks: Array<IntArray>): Int {
        tasks.sortBy { it[1] }
        val on = BooleanArray(2001)
        var ans = 0
        for (t in tasks) {
            var cnt = 0
            for (i in t[0]..t[1]) if (on[i]) cnt++
            var need = t[2] - cnt
            for (i in t[1] downTo t[0]) {
                if (need == 0) break
                if (!on[i]) { on[i] = true; ans++; need-- }
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def findMinimumTime(self, tasks: list[list[int]]) -> int:
        tasks.sort(key=lambda x: x[1])
        on = [False] * 2001
        ans = 0
        for s, e, d in tasks:
            cnt = sum(on[s:e+1])
            need = d - cnt
            for i in range(e, s-1, -1):
                if need == 0: break
                if not on[i]: on[i] = True; ans += 1; need -= 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn find_minimum_time(tasks: Vec<Vec<i32>>) -> i32 {
        let mut tasks = tasks;
        tasks.sort_by_key(|x| x[1]);
        let mut on = vec![false; 2001];
        let mut ans = 0;
        for t in tasks.iter() {
            let cnt = (t[0]..=t[1]).filter(|&i| on[i as usize]).count() as i32;
            let mut need = t[2] - cnt;
            for i in (t[0]..=t[1]).rev() {
                if need == 0 { break; }
                if !on[i as usize] { on[i as usize] = true; ans += 1; need -= 1; }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    findMinimumTime(tasks: number[][]): number {
        tasks.sort((a, b) => a[1] - b[1]);
        const on = Array(2001).fill(false);
        let ans = 0;
        for (const [s, e, d] of tasks) {
            let cnt = 0;
            for (let i = s; i <= e; i++) if (on[i]) cnt++;
            let need = d - cnt;
            for (let i = e; need > 0 && i >= s; i--) {
                if (!on[i]) { on[i] = true; ans++; need--; }
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n * R) where n is the number of tasks and R is the max range of time (<=2000). For each task, we may scan up to R seconds.
  • 🧺 Space complexity: O(R) for the array tracking on-times.