Meeting Rooms II

Data Structures and Algorithms

Statement

Given an array of meeting time intervals intervals, where each interval has a start time and an end time, find the minimum number of meeting rooms needed to hold all meetings. Note, that the end time for each meeting is exclusive.

Constraints

• 1 ≤ intervals.length() ≤ 10³
• 0 ≤ intervals[i][0] < intervals[i][1] ≤ 10⁶

Solution

"""
production algorithm
"""

from algorithms.two_heaps.schedule_tasks_on_minimum_machines.solution import Solution as Solution2


class Solution:
    def find_rooms(self, intervals):
        """
        time complexity O(nlogn)
        space complexity O(n)
        """
        solution2 = Solution2()
        return solution2.minimum_machines(intervals)

"""
unit tests
"""

from unittest import TestCase
from algorithms.merge_intervals.meeting_rooms_2.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.find_rooms(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.find_rooms(tasks)

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

Strategy

Merge Intervals.

Explanation

The problem is the same as Schedule Tasks on Minimum Machines [link]. First, intervals are sorted. Then, intervals are merged. At the end, the number of intervals after being merged is equal to the number of rooms needed to hold all meetings.

Time Complexity

The time complexity of the algorithm is O(nlogn), where n is the total number of intervals.

Space Complexity

The auxiliary space complexity of the algorithm is O(n).

Links

data_structures_algorithms/algorithms/merge_intervals/meeting_rooms_2 at main ·…