Minimum Time to Complete All Tasks solution in Java

Problem Description

Ah, the classic dilemma of managing tasks! You know, like when you have a pile of laundry that’s been staring at you for days, and you think, “I’ll just do it later.” But later never comes, right? Well, welcome to the world of LeetCode, where you’re tasked with figuring out the Minimum Time to Complete All Tasks.

In this problem, you’re given a list of tasks, each defined by a start time, an end time, and a duration. Your mission, should you choose to accept it, is to determine the minimum time required to complete all tasks, while also ensuring that you don’t overlap tasks unnecessarily. Think of it as trying to fit in a Netflix binge between your work schedule—timing is everything!

Code Solution


class Solution {
  public int findMinimumTime(int[][] tasks) {
    final int kMax = 2000;
    boolean[] running = new boolean[kMax + 1];

    // Sort tasks by end.
    Arrays.sort(tasks, (a, b) -> Integer.compare(a[1], b[1]));

    for (int[] task : tasks) {
      final int start = task[0];
      final int end = task[1];
      final int duration = task[2];
      int neededDuration = duration;
      for (int i = start; i <= end; ++i)
        if (running[i])
          --neededDuration;
      // 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 (int) IntStream.range(0, running.length)
        .mapToObj(i -> running[i])
        .filter(r -> r)
        .count();
  }
}

Approach

The approach taken in this solution is quite clever. First, we sort the tasks based on their end times. This allows us to prioritize tasks that need to be completed sooner. Then, for each task, we check how many time slots are already occupied within its start and end range. We then attempt to schedule the task as late as possible, ensuring that we leave room for other tasks to run simultaneously. It’s like trying to squeeze in a quick workout between meetings—timing is everything!

Time and Space Complexity

Complexity Type	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 juggling multiple projects with overlapping deadlines. You have to ensure that each project gets the attention it deserves without causing chaos. By strategically scheduling your time, you can complete all projects efficiently, just like our solution does with tasks.