Linear Scan (Iterative Minimum Finding) complexity?

Time: O(N), where N is the number of tasks. We iterate through the array once to find the minimum element.; Space: O(1). We use a constant amount of extra space for variables like `minTime` and the loop index.. This approach is optimal in terms of time complexity because we must examine every task at least once to guarantee finding the minimum value.

Time: O(N log N), where N is the number of tasks. This is due to the time complexity of most comparison-based sorting algorithms.; Space: O(log N) or O(N), depending on the specific sorting algorithm implementation. Some in-place sorts might use O(log N) for recursion stack, while others like Timsort (used in Python) or MergeSort might use O(N) auxiliary space in the worst case.. While correct and straightforward, this approach is generally less efficient than the linear scan for this particular problem. Sorting performs more operations than strictly necessary, as we only need the minimum element, not the full sorted order.

Earliest Time to Finish One Task

Difficulty: Easy | Acceptance: 84.60% | Paid: No

Topics: Array

You are given an integer array tasks, where tasks[i] represents the time required to complete the i-th task. Your goal is to determine the minimum possible time to finish any single task from the given list. In other words, you need to find the smallest value present in the tasks array.

Examples
Constraints
Linear Scan (Iterative Minimum Finding)
Sorting

Examples

Example 1

Input:

tasks = [[1,6],[2,3]]

Output:

Explanation: The first task starts at time t = 1 and finishes at time 1 + 6 = 7. The second task finishes at time 2 + 3 = 5. You can finish one task at time 5.

Example 2

Input:

tasks = [[100,100],[100,100],[100,100]]

Output:

Explanation: All three tasks finish at time 100 + 100 = 200.

Constraints

- 1 <= tasks.length <= 10⁵
- 1 <= tasks[i] <= 10⁹

Linear Scan (Iterative Minimum Finding)

Intuition

To find the smallest value in an array, we can iterate through each element, keeping track of the minimum value encountered so far.

Steps

Initialize a variable, say minTime, with the value of the first element in the tasks array. This is safe because the constraints guarantee tasks.length >= 1.
Iterate through the tasks array starting from the second element (index 1) up to the end.
In each iteration, compare the current task’s duration (tasks[i]) with minTime. If tasks[i] is smaller than minTime, update minTime to tasks[i].
After the loop completes, minTime will hold the smallest duration found in the array, which is the earliest time to finish one task.
Return minTime.

python

class Solution:
    def earliestTimeToFinishOneTask(self, tasks: list[int]) -> int:
        # Constraints guarantee tasks.length >= 1, so tasks is never empty.
        min_time = tasks[0]
        for i in range(1, len(tasks)):
            if tasks[i] < min_time:
                min_time = tasks[i]
        return min_time

Complexity

Time: O(N), where N is the number of tasks. We iterate through the array once to find the minimum element.
Space: O(1). We use a constant amount of extra space for variables like minTime and the loop index.
Notes: This approach is optimal in terms of time complexity because we must examine every task at least once to guarantee finding the minimum value.

Sorting

Intuition

If the array of task durations is sorted in non-decreasing order, the smallest duration will always be the first element.

Steps

Sort the tasks array in non-decreasing (ascending) order.
After sorting, the earliest time to finish one task will be the element at index 0 of the sorted array.
Return tasks[0].

python

class Solution:
    def earliestTimeToFinishOneTask(self, tasks: list[int]) -> int:
        # Constraints guarantee tasks.length >= 1, so tasks is never empty.
        tasks.sort() # Sorts the list in-place
        return tasks[0]

Complexity

Time: O(N log N), where N is the number of tasks. This is due to the time complexity of most comparison-based sorting algorithms.
Space: O(log N) or O(N), depending on the specific sorting algorithm implementation. Some in-place sorts might use O(log N) for recursion stack, while others like Timsort (used in Python) or MergeSort might use O(N) auxiliary space in the worst case.
Notes: While correct and straightforward, this approach is generally less efficient than the linear scan for this particular problem. Sorting performs more operations than strictly necessary, as we only need the minimum element, not the full sorted order.