Meeting Rooms Leetcode Problem 252 [Python Solution]

Welcome to another Python problem-solving post, we’re tackling the Meeting Rooms problem.

If you’re familiar with LeetCode, you might recognize this as a premium problem.

However, I’ve got a little trick for you to access these premium problems for free on a similar platform called LintCode.

In this problem, we are given an array of meeting time intervals, each consisting of a start time and an end time.

Our task is to determine if a person could attend all these meetings.

To put it simply, we need to check for overlapping intervals.

Before diving into the Python solution, let’s understand the problem and its constraints.

Problem Overview

We’re provided with a list of meeting time intervals in the form of (start, end) pairs.

These intervals represent when a meeting starts and ends.

Our goal is to figure out if it’s possible for someone to attend all the meetings without any schedule conflicts.

The key idea here is to check if there are any overlapping intervals.

If there’s even one overlap, it means that the person can’t attend all the meetings.

If no overlaps exist, it’s possible for the person to attend all the meetings.

Example 1:

Let’s take a look at an example to make things clearer.

Suppose we have the following meeting intervals:

[(0, 30), (5, 10), (15, 20)]

Here’s how we can visualize it:

Meeting 1: (0, 30)
Meeting 2: (5, 10)
Meeting 3: (15, 20)

Now, if we examine these intervals, we can see that Meeting 2 and Meeting 3 overlap.

Specifically, Meeting 3 starts before Meeting 2 ends.

This means that it’s not possible for someone to attend both Meeting 2 and Meeting 3. Therefore, the function should return false.

Example 2:

Now, let’s consider a different set of meeting intervals:

[(5, 8), (9, 15)]

In this case, we have two meetings:

Meeting 1: (5, 8)
Meeting 2: (9, 15)

If we compare these intervals, we can see that they don’t overlap at all.

Meeting 2 starts after Meeting 1 ends, which means that it’s possible for someone to attend both meetings.

Therefore, the function should return true.

Understanding Constraints

Before we jump into the solution, it’s essential to understand the constraints of the problem.

The input consists of meeting intervals, and here are a few things to keep in mind:

The intervals are given as pairs of start and end times.
The start time is always less than the end time in each interval, i.e., (si < ei).

Now that we have a clear understanding of the problem, let’s move on to the solution.

Meeting Rooms LeetCode Problem Solution

Bruteforce Approach

One way to approach this problem is to iterate through all possible pairs of meetings and check if they overlap.

However, this approach would result in an O(n^2) solution, which isn’t efficient.

Fortunately, there’s a more efficient solution.

An Efficient Approach with Sorting

The key to an efficient solution is sorting the intervals based on their start times.

Once the intervals are sorted, you can easily determine if there are any overlaps.

This sorted array provides a straightforward way to check for overlapping intervals.

Here’s a Python solution that implements this approach:

View on GitHub ➹

def canAttendMeetings(intervals):
    # Sort the intervals based on their start times
    intervals.sort(key=lambda i: i[0])

    for i in range(1, len(intervals)):
        i1 = intervals[i - 1]
        i2 = intervals[i]

        # Check if the end time of the previous interval is greater than the start time of the current interval
        if i1[1] &gt; i2[0]:
            return False

    # If no overlaps were found, return True
    return True

Let’s break down this solution step by step:

We start by sorting the given list of intervals using the sort method.

We use a lambda function as the key for sorting.

This lambda function returns the start time of each interval as the sorting key.

After sorting the intervals, we iterate through them.

We start from the second interval (index 1) and compare it with the previous interval (index 0).

We continue this process for all consecutive pairs of intervals.

To check for an overlap between two intervals, we compare the end time of the previous interval (i1[1]) with the start time of the current interval (i2[0]).

If the end time of the previous interval is greater than the start time of the current interval, it means there’s an overlap, and we return False.

If we reach the end of the loop without finding any overlaps, it means that the person can attend all the meetings, and we return True.

This efficient approach works in O(n*log(n)) time complexity due to the initial sorting step, and it’s much more practical than a brute-force approach.

Meeting Rooms Python Code Solution

Let’s put the Python solution into code format:

"""
@param intervals: an array of meeting time intervals
@return: if a person could attend all meetings
"""

def canAttendMeetings(intervals):
    intervals.sort(key=lambda i: i[0])

    for i in range(1, len(intervals)):
        i1 = intervals[i - 1]
        i2 = intervals[i]

        if i1[1] > i2[0]:
            return False
    return True

This Python function canAttendMeetings takes a list of meeting time intervals as input and returns True if a person can attend all meetings without conflicts or False if there are overlaps.

Time and Space Complexity

To wrap up our solution, let’s discuss the time and space complexity.

Time Complexity: The most time-consuming part of our solution is sorting the intervals, which takes O(n*log(n)) time.

After sorting, we perform a linear scan through the sorted intervals, making the total time complexity O(n*log(n) + n), which simplifies to O(n*log(n)).

Space Complexity: Our solution doesn’t use any additional data structures that scale with the input size, so the space complexity is O(1).

Reasoning Behind Our Approach

We’ve chosen the approach of sorting the intervals based on their start times because it allows us to efficiently identify overlapping meetings.

Sorting the intervals simplifies the process of checking for conflicts.

By comparing adjacent intervals in the sorted array, we can quickly determine if there are any overlaps, making our solution both elegant and efficient.

Conclusion

In this guide, we’ve tackled the Meeting Rooms problem, which is all about determining if a person can attend a series of meetings without any schedule conflicts.

We’ve provided an efficient Python solution that sorts the intervals based on their start times and then scans through them to check for overlaps.

As a bonus, I’ve introduced you to LintCode, a platform that allows you to practice premium LeetCode problems for free.

This can be a valuable

resource for honing your coding skills and tackling challenging problems.

Remember, mastering these types of problems is essential for technical interviews, as they test your ability to think critically and devise efficient solutions.

If you found this guide helpful, please like and engage to support the our platform.

If you have any questions, suggestions, or want to discuss other coding topics, feel free to comment below.

Happy coding! 🚀

Question Link: Meeting Rooms on LintCode