Minimum Time to Complete All Tasks solution in C++

class Solution {
 public:
  int findMinimumTime(vector>& tasks) {
    constexpr int kMax = 2000;
    vector running(kMax + 1);

    // Sort tasks by end.
    sort(
        tasks.begin(), tasks.end(),
        [](const vector& a, const vector& b) { return a[1] < b[1]; });

    for (const vector& task : tasks) {
      const int start = task[0];
      const int end = task[1];
      const int duration = task[2];
      int neededDuration = duration - count(running.begin() + start,
                                            running.begin() + end + 1, true);
      // Greedily run the task as late as possible so that later tasks can run
      // simultaneously.
      for (int i = end; neededDuration > 0; --i) {
        if (!running[i]) {
          running[i] = true;
          --neededDuration;
        }
      }
    }

    return ranges::count(running, true);
  }
};
    

Approach Explanation

The approach taken in this solution is quite clever. First, it sorts the tasks based on their end times, ensuring that we can tackle the most pressing tasks first. Then, it uses a greedy strategy to run each task as late as possible, allowing for maximum overlap with other tasks. This way, you can finish your tasks without feeling like you’re in a race against time—because who needs that kind of pressure?

Time and Space Complexity

• Time Complexity: O(n log n) due to the sorting of tasks, where n is the number of tasks.
• Space Complexity: O(k) where k is the maximum time range (2000 in this case) used to track running tasks.

Real-World Example

Imagine you’re a project manager with a list of tasks that need to be completed by your team. Each task has a specific time frame, and you want to ensure that your team is working efficiently. By applying the same logic as in this problem, you can allocate resources effectively, ensuring that tasks are completed on time without overloading your team.

Similar Problems

If you enjoyed this problem, you might also want to check out these related challenges:

• Task Scheduler
• Meeting Rooms II
• Course Schedule
• Minimum Number of Arrows to Burst Balloons
• Partition Equal Subset Sum