Meeting Rooms (LeetCode #920)

Image by Social Cut on Unsplash

This article is part of a series from Nathan Thomas, a full stack software engineer working in San Francisco, CA. Other recent articles from him include Unique Paths and Insert Interval.

Introduction

If you’re looking for a quick walkthrough of an optimal solution to the LeetCode Meeting Rooms problem (it’s a LeetCode premium article, so here’s a LintCode link to get around that), you’re in the right spot.

This is a question in the Blind 75 LeetCode code challenge list, a group of questions put together by a tech lead at Facebook that’s been touted as a great way to prep for interviews.

Don’t beat yourself up too much if you’re here because it gave you a hard time. Everyone has a hard time with coding challenges sometimes.

Let’s get it started! 🙌🏻

Understanding the Problem 🕵🏻‍️

The first thing we should always try to do is understand all the rules for our challenge before writing a single line of code (see Polya’s Problem Solving Techniques):

1. We’ll be given a list of intervals (such as [0, 15]) where the first number is the start time and the last number is the end time
2. This list of intervals will be sorted by ascending order of the start times
3. We need to check if our person can attend all meetings by seeing if any intervals overlap
4. If they overlap, we should return False — if not, we should return True

I’ll be using Python for the answer for this question since it’s a bit like a universal language — whether you prefer JavaScript, Java, Golang, C, or something else, everyone can “kind of” read Python.

We’ll also be jumping straight into an “optimal” solution. If you’re anything like me, you already attempted this problem before searching for an answer. I’m going to make sure you get a good one.

Okay. I think that’s enough housekeeping items for us to get started!

General Approach 🎖

While this problem might seem rough at first glance, it turns out that this problem is extremely straightforward.

It turns out the only thing we really need to do is check each successive interval to see if its start time comes before the previous interval’s end time. That’s it. That’s the solution!

First, we need to write a for loop like this:

We’re going to use the enumerate function in Python because it gives us access to both the index i as well as the value itself (which I’ve named interval).

Next, we need to check each interval and compare it against the last one. Here’s what that looks like:

Whoa. Wait a minute. What’s going on here?

First, we’re pulling out the start value from the current interval value (which would be something like [10, 34]). We don’t need the end value, so I used the _ underscore character which most coding languages (including Python) understand to mean you don’t want to use it but need to include it in order for the destructuring of values off interval to work.

Next, I wrote an if statement to check if index i is greater than 0. We only want to compare intervals if we have a previous one to compare against, right? This means we only want our if statement to run if the index is at least 1.

Finally, I added syntax to the if statement to check that the current interval's start value was less than the previous interval's end value. If this is the case, we can return False. This means that we have found overlapping meeting room times.

If this entire for loop runs over the intervals list without ever returning False, we can know that none of our intervals list has overlapping values. In this case, we can just return True at the end of the function.

That’s it! That’s all it takes! Here it is again if you want to read it:

This entire solution will run in O(n) time complexity (because we’re iterating through the entire list once) and O(1) space complexity (since we’re using a constant number of variables/memory to solve the problem no matter the length of the intervals list that’s passed in).

Conclusion

Great job. How did it go? Did you feel like this one deserved the “easy” title on LeetCode?

Keep an eye out for the rest of these Blind 75 coding challenges articles I’m doing. It’s going to be a fun ride.

Feel free to reach out (using the links below) if you want to talk about coding, cool tech, or anything else (I really like book recommendations).

Thanks for reading. 🔥

Nathan

(GitHub, LinkedIn, Twitter, and Personal Site)