Last active
November 27, 2020 18:24
-
-
Save folksilva/46a756979a4b4cedc841fbeb3193f181 to your computer and use it in GitHub Desktop.
Daily Coding Problem: Problem #21
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
""" | |
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)) |
I am not understanding input here.Could you please explain ?
The first solution from @Balloota is definitely wrong, does not work for (10,15),(10,15) interval, as starting time is the same.
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.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
How about these two different ways. the first in O(n^2) the the second in O(n.log(n))