My Calendar I - Leetcode 729 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today I'll solve the problem my calendar 1 the idea is pretty simple we're given a class to implement and the reason we're given a class is because we're going to manage like the state of something that's going on we only have one function to actually implement it is called the book function and it's going to give us two integers a start integer and an end integer and we can guarantee that the start is all way going to be less than the end so we can think of this kind of as an interval problem suppose the first time it's called we're given a range of 10 to 20 those are the two integers that we're given we're going to be given more ranges these are pretty much events in our calendar and as long as the events that were given don't overlap we should be good we can just kind of add that to our list of events and then we can return true if they do overlap which would only be the case if one of the points is actually within the other point so like let's say we had something like 15 uh to 25 which actually is the second event here that we're given for this event there is some overlapping like you could say that this is in between this one or you could say this is in between that one so for this one we would not add it to our list because it overlaps with an existing one and we would return false now the third event that's given to us is this one one 20 to 30 by my definition the one that I kind of gave this one is definitely not between this one and this one is not between this one they are equal and that's actually perfectly fine so the way that they Define it in this problem is by saying that the ending point is always open-ended so I drew this one with a closed Circle but I want it to be an open circle so that's actually available and then so this one the starting is closed but the ending is going to be open so kind of like this so the simplest way to solve this problem is to just throw all of these events into a list or an array adding the event if we just add it to the end is technically going to be constant time but to determine if two events overlap we are going to have to scan through that entire input so whatever the size of it is let's say you know it's M for that's how many events have already happened the time complexity would be n time M now it's better to kind of put this in just in terms of n like let's say our function is called 10 times the time complexity of that is going to be proportional to the size of the list which could be up to 10 so if we replace this with a variable let's say n then we can say that the overall time complexity is n^ s so this is one valid solution so I'll code this up now before I show you a more optimal one so I'm going to have a list in my Constructor I'm going to call it events so in Python we can do that like this this is a member variable and then within our book function we're going to first scan through the list of events we could do it like this for event in events but in Python you can unpack the events because we're going to store them like this it's going to be a starting and an ending event we're going to store it as a tupal or you could also store it as like a nested list but we're going to unpack those like this SE and then we want to know if they're overlapping because if there's some overlapping we're going to return false if they're not overlapping then we're going to go through the entire list and if none of them overlapped with the current event then here we're going to return true but not before we add that event to our list of events so like this start end now how do we determine if they overlap one way is to determine if they don't overlap we know that they don't overlap let me just kind of draw a couple like events um this is like the opening something like this I know this isn't like a great drawing but these two don't overlap because the starting of one of them is greater than the ending of the other I guess they could also be equal so let's account for that let's say the start of the current event is greater than or equal I'll do it like this is greater than or equal to the ending of the other event that's one case where they don't overlap like we can kind of guarantee that now suppose that like the current event this time is actually this one well then we could say the ending of that event is actually less than or equal to the start of the other event so if either of these two are true then we guarantee that they don't overlap but this is the case where they do overlap so we can just take the negation of this whole thing just put a knot in front of it like this and so if we run this now that's pretty much the whole code whoops uh for events here I forgot to reference it with the self keyword and when appending here I forgot to use the actual append method sorry about that but you can see that this solution does work it's relatively efficient if you wanted to simplify this a little bit if you kind of know how like Boolean math works like we're saying that either of these is not true like both of them are not true then like evaluate this portion of the code so we could kind of take that and distribute it to both of them and then put an and here so if both of these are not true we can make um them the opposite just by changing the sign so this is less than or equal we can change that to a greater than and then this this is less than or equal we can change that to a greater than and then this will technically work as well just to prove it you all run it um yep it's the same solution pretty much but now I'm going to show you a different solution now you might already be thinking instead of just having these ranges like these events in random order in our list why don't we maintain a sorted list then we could look up the list to check for two overlapping intervals in log and time but the problem is maintaining the sorted order we'd have to insert potentially in the middle of that list and and that is going to be a linear time operation so doing that with an array isn't going to work but we can use a data structure that has pointers you might be thinking like a linked list but actually there's a much better and more intuitive data structure pretty much the binary search tree it's a very natural data structure to use for this and the way we're actually going to use it each node is going to have a range so it's going to be kind of similar to doing a segment Tre not exactly and we're only going to be doing the insertion portion of that not doing any lookups or deletions or anything super complicated so it actually won't be a super difficult solution to implement this is the idea we start with an empty binary search tree if it's empty then the first event that we try to add is always going to work so we add a node it has a range 10 20 now you can probably guess what I'm about to do if this is the root node we're going to say that everything in the right subtree is going to be strictly greater than 20 well I guess it could be greater than or equal so if we had like another event that's like 20 to 30 that's fine cuz they're equal but it can't be less similar on the left side we are going to allow events that look like this let's say 5 to 10 cuz the ending of this event can be equal to the beginning of the next event but they can't be greater like no value in this entire sub tree can be greater than 10 and so that's how we can guard against having overlapping um events the only problem is that if we implement this binary search tree ourselves creating like the self balancing portion is going to be tedious so like we can skip that but that doesn't guarantee that the insertions are going to be log n cuz in an unbalanced binary tree we know that that can actually be Big O of n because it's determined by the height of the tree not the number of nodes but anyways I think this is still an improvement over the previous one so this is what we're going to do we have this the next one we try to do is going to be 15 to 25 how would we do the comparisons well the compar are going to be exactly the same as we did before first we're going to check is the beginning of this new Range greater than or equal to this one if it is then we're going to follow the right pointer and then maybe we'll arrive at a new node and we'll kind of keep doing that recursively well not recursively but just by following the pointers now if that's not the case let's try the other direction perhaps this value is less than or equal to the beginning of the other value well it looks like that's not the case either this is not less than that so that doesn't work either so that's how you know that these two intervals are overlapping and then at that point we can just immediately return false otherwise uh we would follow the pointer and we'd either see over here or over here that we've gotten to a null pointer and that's when we can create a new node with the given range and then do the insertion and if this was nonnull we would just have followed the pointer and then kept going until we reached a null pointer this isn't like super complicated it's just implementing the insertion of a binary tree with just a little bit of range checking but let's go ahead and code this one up so up above I'm going to declare my tree data structure that's kind of what this solution is going to be all about we're going to have our Constructor and we are going to have our insert method as well so insert is going to be given a start and an ending range and even the Constructor is actually going to be given that as well cuz I'm not going to have a separate class for the tree node I could do that if I wanted to but just to kind of keep this more concise I'm not going to do that so I'm going to pass in the start and ending here within the tree itself I'm going to maintain two things the left child which initially is going to be null the right child which is initially also going to be null and the starting and ending of the current node so the starting is going to be the given value and same thing with ending so now that we kind of know the structure of this assume that the insert method is going to work and I'm going to fill in the rest of this code down here and then we're actually going to implement the insertion so in our Constructor just to make sure that these interfaces are going to work we should just try to implement the solution so here I'm going to maintain the root of the calendar the root node initially it's going to be null and then when I'm given an event to book I'm going to first check if not root well let's use the self keyword if this is nonnull let's go ahead and create a tree node with the given start and end values and then let's set that to the root node the first event that we book is always going to work right we always expect that to work so here we'll return true now if it's nonempty well then let's do self. root. insert into the existing tree this range and let's say that this insert is either going to return true or false we can just return the result of that method call so now that we have that the only thing left to do is fill in the insert and and this can be done iteratively it's just like inserting into a regular binary tree so I'm going to have a pointer initially I'm actually going to set it to just self so it's pretty much like the instance of this object and then I'm going to do just while true eventually we're going to either reach like a conflict which will return false from here or we will do the insertion and then we'll return true so we don't really need like a condition that's going to terminate but now let's do the comparisons if the start is greater than or equal to the current nodes ending so current do end then let's follow the right pointer we can say current is going to be current. right else if the opposite is true if the ending of the current range is less than or equal to the start of the other one let's follow the other pointer current is going to be equal to current. left else there's a conflict in which case we return false so now where exactly are we doing the insertions well before we shift the pointer here what if the right child is actually null well before we get there let's do the insertion so let's check if not current. right let's then say okay we reached the bottom of the tree we reached the point where we can insert the new node so we'll say current. WR can now be set to a new tree node with the given start and end and here we can then just return true and then do the opposite over here if not current left let's then do the insertion current. left is equal to this and after that we can go ahead and return so this is like the bulk of the solution but it's nothing super complicated as you can see so I'm going to go ahead and run it and you can see this one works and is definitely more efficient even the worst case is technically o of n assuming that the ranges are given like in a random order the tree should be balanced and it should be log n if you found this helpful check out n code. thanks for watching and I'll see you soon