Schedule Tasks on Minimum Machines

Data Structures and Algorithms

Statement

Given an input array tasks of start and end times, find the minimum number of machines required to complete the tasks.

Constraints

• 1 ≤ tasks.length() ≤ 10³
• 0 ≤ tasks[i].start < tasks[i].end ≤ 10⁴

Solution

"""
production algorithm
"""

from data_structures.heap.heap import Heap


class Solution:
    def minimum_machines(self, tasks):
        """
        time complexity O(nlogn)
        space complexity O(n)
        """
        start_times, end_times = Heap(), Heap()

        # sort tasks by earliest start time
        for task in tasks:
            start_times.push(task)
        _, end = start_times.pop()
        end_times.push(end)

        # merge tasks by earliest end time
        # and next start time
        while not start_times.empty():
            start, end = start_times.pop()
            if end_times.top() <= start:
                end_times.pop()
            end_times.push(end)

        return end_times.size()

"""
unit tests
"""

from unittest import TestCase
from algorithms.two_heaps.schedule_tasks_on_minimum_machines.solution import Solution


class SolutionTestCase(TestCase):
    def test_sequential_tasks(self):
        # Given
        tasks = [(1, 3), (5, 7), (9, 11), (13, 15), (17, 19)]
        solution = Solution()

        # When
        actual = solution.minimum_machines(tasks)

        # Then
        expected = 1
        self.assertEqual(actual, expected)

    def test_nonsequential_tasks(self):
        # Given
        tasks = [(1, 3), (2, 4), (5, 7), (6, 8), (9, 11), (10, 12)]
        solution = Solution()

        # When
        actual = solution.minimum_machines(tasks)

        # Then
        expected = 2
        self.assertEqual(actual, expected)

Strategy

Two Heaps.

Explanation

First, sort the tasks by earliest start time. Sort the tasks in a min heap. Next, merge tasks in a second min heap, if the task with the earliest end time ends before the task with the earliest start time, then merge the tasks. Merged tasks can be completed on the same machine. Finally, the number of merged tasks is the number of machines needed to complete all tasks.

Time Complexity

The time complexity of the algorithm depends on the time to insert or remove all tasks in a heap. Therefore, the time complexity of the algorithm is O(nlogn).

Space Complexity

The auxiliary space complexity of the algorithm depends on the size of the heaps and is O(n).

Links

data_structures_algorithms/algorithms/two_heaps/schedule_tasks_on_minimum_machines at main ·…