Count Days Without Meetings - Leetcode 3169 - Python

Key Takeaways

Hey everyone, welcome back and let's write some more neat code today. So today, let's solve the problem count days without meetings. Pretty interesting problem actually. So the idea is that we're kind of given a range. This is sort of an interval problem. If you're not familiar with these, highly highly recommend checking out Node.io. I know that most of you guys probably already do, but I would go to the uh interval section in this page because the first few problems are going to give you a pretty good introduction to this sort of pattern. Some of them can get pretty difficult, but once you know this pattern, it actually turns out to be pretty easy. So that's what I'm going to try to show you today. So in this specific example, they are giving us two parameters. One is going to be the actual interval. So here you can see we have a bunch of meetings. One of the meetings looks like this. 57. That means that from day five to day 7 there's going to be a meeting ongoing and the end points are inclusive in this case. So if we were to draw that interval out up here I think it would look something like this from 5 to 7 with a closed circle. We could add the other intervals as well. 1 3 9 10 and the last one over here on the right. So in this example, you can see that none of these intervals are actually over overlapping. That's the key word here. And they actually tell us that that's not always going to be the case. The meetings might overlap. And that's where the challenge is going to come in. That's where things are going to get interesting because in this problem, not only are we given these intervals, we're also given a total range. That's why I drew this from 1 to 10 because they tell us we only care about 10 days. day one, day two, day three, etc., etc., up until day 10. And specifically what we want to count, and I just realized that I messed up my one, three, and I also kind of messed up this drawing, which I think is actually a good mistake to make because look at this drawing. What I wanted to do was represent each of these as like a single day. Like this is a day, this is day two, this is day three, four, five, 6, 7, 8, 9, 10. Right? That's what I wanted to do. It looks correct. But the mistake is this. When I drew the lines here, I put the number next to each line. I have 11 lines. I have 1 2 3 4 5 6 7 8 9 10 11 lines. So, that's the mistake that I made, but I think it's a good one. So, I'll probably leave it in the video. So to fix this, what we could do is just move this one over here and extend this over here because now this represents one, this is two, this is three, this is four. Uh this five belongs over here. So let's uh quickly try that again. Okay, so now 57 I'm going to do this part from five to six to 7. So this is 5 seven here and here will have the end points. We're also going to do 1 three. So 1 2 3. So that's our other interval. And then lastly we will have 9 10. It should be an interval of length two. Okay. Now this is looking a lot better. Now they told us we have 10 days total. What they want us to return down there is how many days were actually free. How many days did not have any sort of meeting. So with this example, the problem seems almost too easy. It seems almost too trivial because what we would do is we just go through the intervals in any order. It doesn't matter. We see that they might not be sorted in the input. So we can just go through them randomly. We'd go through every single interval. Okay, let's look at this one. It goes from five all the way to 7. How do I get the length of this interval? Well, I can do seven minus 5. And to that I'm going to add a + one because this is clearly of length three. So that's why we do it. So this interval is of length three. This interval is of length two. This interval is also of length three. I take all these up. I add them. I get eight. I take the days I started with 10. And then I subtract it and then I get two. So it seems really easy, seems trivial, but it gets more interesting when the intervals start to overlap. So let's consider an example like that. So let's say we start with something like this. And uh to pick an interesting one, let me put a little interval over here. So it's going to be going from three to four all the way to five. So now we got some over overlapping going on. And this is where just the general pattern of how intervals work is going to be applied here. What we're going to do is we want to start all the way at the left and then we want to go interval by interval. With the first one, it's pretty easy. This is what we're going to do. We're going to look at the first interval all the way on the left and I'm going to say, okay, length of this looks like three. It's definitely not overlapping with anything that came before it because nothing came before it. So I take this, I subtract it from 10. So my days are 10. Now I'm going to minus three from that. Okay. So next we're going to look at the next interval in sorted order. The naive thing to do at this point would be to get the length of this interval as well, which is once again three, and then subtract that from the total number of days. But here's the problem. This interval as you can see over here is overlapping this specific uh day. It looks like it's day three overlaps with this one. How do we know that? How would we know that it over overlapped with something that came before it? Well, we keep track of something. I'm going to call it the previous end, but really it's going to be the furthest end day that we've encountered so far. So at this point it was clearly day three because on day three it was the last day. So what we instead do to compute the length of this interval, we want to actually start from over here where the previous end actually was. So what that really means is we're actually only left with days four and five over here. Now you might be wondering, well this interval also overlaps with the one that comes ahead of it as well. But that's okay because when we get to this interval once again we're going to start at the previous end. We're not going to take account in the fact that like this overlapping region we will not include that in our calculation. Okay. So now once you understand like this conceptually it becomes easier. The only hard part left is that there's like some edge cases and like calculating it can be kind of tricky. So this is how we're going to do it. We have the previous end. It's three. My current interval right now is this 35. So my start is actually the same as the previous end. In a sense, we can say that that is overlapping. We would rather start at the previous end plus 1. So in other words, what I'm saying is I know my interval is 35, but actually I want my interval to be something else. I want to say that yes, my interval ends at 5, but it actually doesn't start at 3. I'm gonna say it starts at the previous end plus one, which is four. But that's not always going to be the case. Maybe the previous end could have been really small. It could have been one. In that case, one is smaller than our current end. So that's fine. We start at three. So in other words, the calculation is going to be this. We're going to have our current end. That's fine. But our start is going to be different. Our start is going to be the max of our current start. So let me kind of draw that here. The max of our current start as well as the previous end plus one. We have to do the plus one because we can't include that day itself. Okay. So this gives us the start. So then our interval in this calculation will become four. So we'll start at four and end at five. Now how do we get the length of this interval? Well, once again, just take 5 minus 4 + 1. So that's pretty much it. That's the calculation. Meaning in this interval, we will get the correct calculation of two. So here we will do a subtract two. That's from the blue region. And then lastly, uh we will update our previous end because we see that our current end is five. That's greater than three. Go ahead and update it. Now it's going to be five. Lastly, we get to the last interval. It's 57. We will do the same sort of calculation that we did to get the actual starting point. We know the ending point here is 7 and the starting point is five. But the previous end was five. So actually we have to start at 6 plus or 5 + 1 which is going to be six. So this is the actual portion of the interval. And once again we do the calculations 7 - 6 + 1 we will get a -2 over here as well from the orange region. You calculate all of this you get 10 - 7 which is 3. And that looks uh correct to me because we do have 1 2 3 days over here at the end. So this works. There's one last edge case that I didn't mention and it has to do with sort of the shape of these intervals. Can you imagine that maybe a following interval might end before the previous interval? Like maybe this blue interval will actually extend really far, but the starting point comes before the starting point over here. And I don't think I mentioned this earlier, but since we are scanning through these from left to right, we're scanning through these intervals sort of in sorted order. Sorted by the starting value of each interval. So it's very important to sort the input if you actually want to scan through it in this order. Only then are we allowed to run this sort of algorithm that I'm talking about. So how is this example going to work? Let's see how our current algorithm would calculate this. It looks like it's going to probably be a problem because what we're going to get is okay this was my uh previous interval. So it looks like a previous end was equal to 9 over here. And now my current interval which is the orange one which is 57. I want to know what's my starting point. Okay, it's going to be previous + one because that's you know bigger than this. Okay, so my real start is going to be 10. That kind of makes sense because like that's where we have to start. But then we go to 7. So the length of this interval is going to be 7 - 10 + 1. That's negative. So that's not going to work. If we ever get a length that is less than zero, we don't care about it. So in a way, just if it's negative, just reset the length back to zero because then um subtracting zero from the days won't do anything. So with this, we can solve this problem pretty efficiently. This main portion of the algorithm just scanning through is going to be linear time and I believe constant space. Um, but most of the complexity is going to come from sorting the meetings, which I guess is going to be n login and that might take extra uh space complexity depending on the language that you're using or the sorting algorithm. So, let's code it up. So, I'm not going to lie, the code is going to look pretty easy, but that doesn't mean the problem is. So, if you struggle with this, please don't feel bad. You should have seen me when I was learning this. But anyways, I'm going to sort the input. I'm going to track my previous end. Initially, I could set it to zero or negative 1 because I think our meetings are going to start at day one and then go up until this day. Then I'm going to go through every meeting in the list of meetings. And while I'm doing that, we know that each meeting is a pair. I might as well unpack it here since Python makes that pretty easy for us to do. I got the start and I got the end of the current meeting. I want to get the length of the meeting. But to get the length, I have to update potentially the start. Remember we determined that the start should be the max of itself and the previous uh end plus one. That's where we have to start at. Clearly we can't start at previous end. That's already been used. So we have to start at the next day. And to calculate the length then becomes pretty easy. End minus start + 1. And after that it becomes pretty easy to update the days. Just subtract from it the length. But what if the length was zero or negative? That's okay. Pretty easy to deal with that. Here's a little trick if you didn't know it. Take the max of that length and zero. So now if the length is zero or negative, well, this will evaluate to zero. So this won't do anything. That's fine. And then after we're done with that, we just return the number of days. This might be the first time I coded something without having a result variable, but they made it easy for us just by giving us the days. So I'll run this. Oh, whoops. Uh, very, very trivial mistake. We forgot to update the previous end. So, after all this is said and done, let's potentially update the previous end. We want it to be the max of itself and the current end. So, there's the last line of code. So, now you can see that this code works. And I mean, I'm pretty sure that it's efficient. I think that this is misleading. I mean, let's look at some of these and see if they did things any different. Okay, never mind. Maybe maybe some people are doing things differently. It looks like it actually is possible to solve this problem without sorting. No, it looks like they actually are sorting down here. So, I'm honestly not sure, but I'm pretty sure my code is probably just as efficient as this. Let's run this code just to make sure. Yeah. So, I guess his code is a little bit more efficient, but it's like 50 or 60 milliseconds. I have no idea why that is. They're using a hashmap. It seems like it shouldn't be the case, but I don't think this really makes much of a difference because I think in a real interview, I think my code would probably be considered fine. And I think the big O runtime is the exact same. So anyways, if you found this helpful, check out necode.io for a lot more. Practice up on some interval problems and you'll be an expert before you know