Daily Coding Problem: Problem #21

problem21.py

"""
This problem was asked by Snapchat.

Given an array of time intervals (start, end) for classroom lectures (possibly overlapping), find the minimum number of rooms required.

For example, given [(30, 75), (0, 50), (60, 150)], you should return 2.

https://dailycodingproblem.com/
"""
import itertools

def minimum_rooms(lectures):
    input_data = [' '.join(str(j) for j in i) for i in lectures]
    combinations = set()
    rooms = 0
    for c in itertools.combinations(input_data, 2):
        a = set(range(*(int(n) for n in c[0].split())))
        b = set(range(*(int(i) for i in c[1].split())))
        if not a.intersection(b) == set():
            rooms += 1
    return rooms if rooms > 0 else 1


if __name__ == "__main__":
    # Read the number of lines to read
    rows = int(input())
    lectures = []
    for i in range(rows):
        lectures.append([int(n) for n in input().split()])
    print(minimum_rooms(lectures))

With the given solution, intervals [(10,20), (15,25), (25,30), (20,30)] return 3. Is this not supposed to be 2 ?

def minimum_rooms(intervals):
   '''
   Inspired by
   https://medium.com/javascript-in-plain-english/snapchat-coding-interview-questions-377fc67e0cbe
   '''

    starting_times, ending_times = [], []

    starting_times = [i[0] for i in intervals]
    ending_times = [i[1] for i in intervals]

    starting_times.sort()
    ending_times.sort()

    starting_index = ending_index =  0
    max_rooms = current_rooms = 0

    while starting_index < len(starting_times) and ending_index < len(ending_times):
        if starting_index >= len(starting_times):
            break

        if starting_times[starting_index] < ending_times[ending_index]:
            current_rooms += 1
            starting_index += 1
        else:
            current_rooms -= 1
            ending_index += 1
        
        max_rooms = max(max_rooms, current_rooms)

    return max_rooms


intervals = [(30, 75), (0, 50), (60, 150)]
assert minimum_rooms(intervals) == 2

intervals = [(5, 7), (0, 9), (5, 9)]
assert minimum_rooms(intervals) == 3

Please explain the ques.