#2589

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Minimum Time to Complete All Tasks

Determine the minimum active time for a computer to complete all scheduled tasks within their specific time windows efficiently.

array binary search stack greedy sorting

Problem Statement

You are given a list of tasks represented as tasks[i] = [starti, endi, durationi], where each task must run for durationi seconds within the inclusive time window from starti to endi. The computer can execute multiple tasks simultaneously, but you aim to minimize the total time it stays on.

Design an algorithm to determine the minimum number of seconds the computer needs to be active to complete all tasks. Tasks may be split across their time ranges and executed non-continuously, requiring careful scheduling to optimize the active duration.

Examples

Example 1

Input: tasks = [[2,3,1],[4,5,1],[1,5,2]]

Output: 2

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

Input: tasks = [[1,3,2],[2,5,3],[5,6,2]]

Output: 4

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 Approach

Sort tasks by end time

First, sort all tasks based on their end time. This allows the greedy selection of available time slots while checking feasibility for a candidate active time in the binary search.

Binary search over active time

Apply binary search on the total active time. For each candidate time, attempt to schedule all tasks within their windows using a stack or priority mechanism to track available slots. Adjust search bounds based on feasibility.

Greedy allocation within ranges

Within each candidate active duration, allocate task time greedily from the latest available moment backward. Use arrays or stacks to mark scheduled seconds, ensuring each task reaches its required duration without exceeding the candidate total time.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the number of tasks and the range of possible active durations; sorting adds O(n log n), binary search adds O(log(maxTime)), and scheduling feasibility checks add O(n*maxDuration). Space complexity depends on tracking scheduled seconds, which may require O(maxEnd) arrays.

What Interviewers Usually Probe

Sorting by end time hints at a greedy or scheduling approach.
Binary search over the answer space signals optimization beyond naive simulation.
Attention to non-continuous task allocation is critical for passing edge cases.

Common Pitfalls or Variants

Common pitfalls

Failing to account for tasks split across non-continuous time windows can underestimate required active time.
Using naive simulation without sorting can lead to incorrect schedules and timeouts.
Not updating or tracking already allocated seconds properly can result in double-counting active time.

Follow-up variants

Tasks have fixed durations but allow preemption in arbitrary time slices within the window.
Compute minimum active time with additional constraints like maximum simultaneous tasks.
Change the problem to maximize tasks completed within a fixed total active time.

FAQ

What is the main approach for Minimum Time to Complete All Tasks?

The primary strategy is binary search over possible active durations combined with sorting tasks by end time and greedy allocation.

Can tasks be split across non-continuous seconds?

Yes, each task can be executed in multiple segments within its allowed time window, which is essential for minimizing active time.

Why sort tasks by end time?

Sorting by end time ensures that greedy allocation can fill later slots first, reducing conflicts and helping binary search find feasible schedules efficiently.

How does binary search over valid answers work here?

Binary search tests candidate total active times; for each, a scheduling simulation checks whether all tasks can be completed within the candidate duration.

What are common mistakes in this problem?

Typical errors include double-counting active seconds, ignoring non-continuous execution, and failing to properly track allocated slots during feasibility checks.

terminal

Solution

Solution 1: Greedy + Sorting

We observe that the problem is equivalent to selecting $duration$ integer time points in each interval $[start,..,end]$, so that the total number of selected integer time points is minimized.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def findMinimumTime(self, tasks: List[List[int]]) -> int:
        tasks.sort(key=lambda x: x[1])
        vis = [0] * 2010
        ans = 0
        for start, end, duration in tasks:
            duration -= sum(vis[start : end + 1])
            i = end
            while i >= start and duration > 0:
                if not vis[i]:
                    duration -= 1
                    vis[i] = 1
                    ans += 1
                i -= 1
        return ans

Continue Practicing

#2576 find the maximum number of marked indices #2616 minimize the maximum difference of pairs #2554 maximum number of integers to choose from a range i