#toyprogrammingchallenge
Here's a freebie!
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.
@Absinthe i am nor programmer, nor engineer, nor mathematician but in the array you put for the example i see two lectures that do not overlap, so, they can be celebrated in the same classroom and the (30, 75) one overlaps the others, so it can not be in the same classroom. But i do not know how to generalize this or how to code this problem solver...
@mikelga You can look at the lectures as having a StartTime and an EndTime and so if a lecture has a StartTime that is greater than the StartTime of another and less than the EndTime of that same one then they overlap. If one's start time is greater than another's EndTime then they don't overlap.
The number of rooms you would need depends on the overlaps. If you have no overlaps then you only need one room. Each overlap may require an additional room. If one overlaps multiple other rooms, then once you have accounted for it having a room, you start the rule over for the rest of the rooms. For an example:
a = 1 to 5
b = 4 to 6
c = 7 to 9
If you provide a room for b you can server a and b with a single extra room.
If you provide a room for b then A and C will still overlap.
a = 1 to 5
b = 2 to 7
c = 4 to 9
Does that help clear it up?
@mikelga I was thinking about this earlier.
So you take your first lecture, and assign it to a room
Then you rake your next one, and if it is an overlap you put it in a new room, otherwise put it in the same room.
Then take the next one, if it only overlaps one of the ones in the first room, then whichever one was earlier goes in the room and the one that gets displaced then goes it gets tested against the next room. and so on down the line. When you are out of lectures, count up the rooms.
@Absinthe yes it is clear. If i understood well, always the number of classrooms we need is, the number of overlaps plus one. First we have to find how many overlaps occurs and then add 1. If no overlaps it is like this 0 + 1 and if there are overlaps, call it n. Then the total of classrooms needed are n + 1.
For me the hard part of this problem is to find out how many overlaps occurs using a no drawing method 🤨
Thank you!