252. Meeting Rooms

Problem Description

The problem presents a scenario in which an individual has multiple meetings scheduled, represented by time intervals. Each interval is an array of two values [start_i, end_i], where start_i is the time a particular meeting begins, and end_i is the time the meeting ends. The intervals array contains all such meeting time intervals.

The task is to determine whether the person can attend all the scheduled meetings without any overlaps. More specifically, no two meetings can occur at the same time. The person can only attend all meetings if, for any two meetings, one finishes before the other starts.

Intuition

To solve this problem, it is essential first to understand that if the person can attend all meetings, then there cannot be any overlap between the time intervals. In other words, the end time of a meeting must be earlier than or equal to the start time of the subsequent meeting.

The intuition behind the solution is to first sort the meetings based on their start times. Sorting the meetings ensures that they are arranged sequentially, which makes it easier to check for any overlaps.

Once the meetings are sorted, we need to compare the end time of each meeting with the start time of the next one in the list. This is where the pairwise function is beneficial. It creates pairs of consecutive elements (in this case, meeting time intervals). We simply iterate through these pairs and check if the end time of the first meeting (a[1]) is less than or equal to the start time of the next meeting (b[0]).

By using the all function, which verifies that all elements in an iterable satisfy a particular condition, it is possible to ensure that for all pairs of consecutive meetings, the first one ends before the second one begins. If this condition is true for all pairs, the function returns True, and hence, the person can attend all meetings. Otherwise, it returns False, indicating a conflict in the meeting times.

Learn more about Sorting patterns.

Solution Approach

The solution's algorithm follows these steps:

Sorting the intervals: The input list named intervals is sorted in-place. Since intervals consists of sub-lists where each sub-list represents a meeting time interval [start, end], the sort() method by default sorts the sub-lists based on the first elements, which are the start times of the meetings. This is crucial because it orders the meetings in the way they will occur through the day.
Checking intervals in pairs: After sorting, the pairwise function from Python's itertools is used to create an iterator that will return tuples containing pairs of consecutive elements (or intervals in this case). This means if the sorted intervals list has elements [a, b, c, d, ...], pairwise(intervals) would give us an iterator over (a, b), (b, c), (c, d), ....
Using a generator expression with all: The code includes a generator expression all(a[1] <= b[0] for a, b in pairwise(intervals)) which iterates through every pair of consecutive meetings from the iterator and checks if the end time of the first meeting (a[1]) is less than or equal to the start time of the next meeting (b[0]). The function all will return True only if every evaluation within the expression yields True, meaning that there are no overlapping meetings. If any meeting overlaps, meaning the end time of one meeting is later than the start time of the following meeting, the expression will yield False, and thus the all function will short-circuit and return False.
Returning the result: The boolean result from the all function is returned directly. If the result is True, it means all the meetings do not overlap, and the individual can attend them all. If the result is False, it means there is at least one overlapping pair of meetings, which makes it impossible for the person to attend all of them.

In summary, this solution effectively leverages sorting and simple comparisons in pairs to determine whether meeting intervals overlap. The use of the all function along with a generator expression makes the implementation concise and efficient.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider the following small example to illustrate the solution approach:

Assume we have the following meeting time intervals:

intervals = [[0, 30], [5, 10], [15, 20]]

Here, we have three meetings scheduled:

Meeting 1 from time 0 to time 30.
Meeting 2 from time 5 to time 10.
Meeting 3 from time 15 to time 20.

Now, let's go through the solution step by step:

Sorting the intervals: We sort the intervals based on their start times:

intervals.sort()  # Result: [[0, 30], [5, 10], [15, 20]]

After sorting, the order of intervals does not change because they were already sorted by their start times by default.

Checking intervals in pairs: We use the pairwise function from Python's itertools to consider the intervals in pairs for comparison:

from itertools import pairwise
# This pseudo operation would create iterator pairs: ([0, 30], [5, 10]), ([5, 10], [15, 20])

Using a generator expression with all: We then construct a generator expression with the all function to check for overlaps:

all(a[1] <= b[0] for a, b in pairwise(intervals))
# This checks: 30 <= 5 (for [0, 30], [5, 10]) and 10 <= 15 (for [5, 10], [15, 20])

During iteration:

The first pair ([0, 30], [5, 10]) is evaluated. Since the end time of the first meeting 30 is not less than the start time of the second meeting 5, the condition a[1] <= b[0] is False. Therefore, the all function would return False.
Because all short-circuits (stops evaluating) as soon as it encounters a False, the result is determined without needing to evaluate the second pair ([5, 10], [15, 20]).

Returning the result: The generator expression would return False, indicating that the person cannot attend all meetings because at least one pair of meetings overlaps.

In this example, the meetings at intervals [0, 30] and [5, 10] are overlapping, which means the person cannot attend both meetings. So the result for whether the individual can attend all meetings is False.

Solution Implementation

1from typing import List
2from itertools import tee
3
4class Solution:
5    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
6        # Function to generate consecutive pairs in a list
7        def pairwise(iterable):
8            "s -> (s0,s1), (s1,s2), (s2, s3), ..."
9            a, b = tee(iterable)
10            next(b, None)
11            return zip(a, b)
12      
13        # Sort the intervals based on their start times.
14        intervals.sort()
15      
16        # Check if there is any overlap between consecutive intervals.
17        # If the end time of the first interval is greater than the start 
18        # time of the second interval, they overlap, which means 
19        # one cannot attend all meetings.
20        # The `all` function returns True if all comparisons are True.
21        return all(end_time <= start_time for (start_time, end_time), (next_start_time, _) in pairwise(intervals))
22

1class Solution {
2
3    // Function to check if a person can attend all meetings
4    public boolean canAttendMeetings(int[][] intervals) {
5      
6        // Sort the intervals based on the start times
7        Arrays.sort(intervals, (interval1, interval2) -> interval1[0] - interval2[0]);
8      
9        // Iterate through the sorted intervals to check for any overlaps
10        for (int i = 1; i < intervals.length; ++i) {
11            // Get the current and previous intervals
12            int[] currentInterval = intervals[i];
13            int[] previousInterval = intervals[i - 1];
14          
15            // If the end time of the previous interval is greater than the start time of the current one,
16            // they overlap, so it's not possible to attend all meetings
17            if (previousInterval[1] > currentInterval[0]) {
18                return false;
19            }
20        }
21      
22        // If there are no overlaps, the person can attend all meetings
23        return true;
24    }
25}
26

1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    // Function to determine if a person can attend all meetings
7    bool canAttendMeetings(std::vector<std::vector<int>>& intervals) {
8        // Sort the intervals based on their start times
9        std::sort(intervals.begin(), intervals.end(), [](const std::vector<int>& a, const std::vector<int>& b) {
10            return a[0] < b[0];
11        });
12
13        // Loop through the intervals to check for any overlaps
14        for (int i = 1; i < intervals.size(); ++i) {
15            // If the current interval's start time is less than the previous interval's end time
16            if (intervals[i][0] < intervals[i - 1][1]) {
17                // Overlap detected, cannot attend all meetings
18                return false;
19            }
20        }
21      
22        // No overlaps found, can attend all meetings
23        return true;
24    }
25};
26

1/**
2 * Determines if an individual can attend all the given meetings.
3 * Meetings are represented by intervals where each interval is an array of two integers,
4 * with the start time as the first element and the end time as the second element.
5 * 
6 * @param {number[][]} intervals - A list of intervals representing meetings.
7 * @returns {boolean} - Returns true if an individual can attend all meetings without
8 *     any overlaps; otherwise, returns false.
9 */
10function canAttendMeetings(intervals: number[][]): boolean {
11    // Sort the intervals based on their start time.
12    intervals.sort((a, b) => a[0] - b[0]);
13
14    // Iterate over the sorted intervals starting from the second interval.
15    for (let i = 1; i < intervals.length; i++) {
16        // Check if the current interval starts before the previous interval ends.
17        // If so, there's an overlap, and the person cannot attend all meetings.
18        if (intervals[i][0] < intervals[i - 1][1]) {
19            return false;
20        }
21    }
22
23    // If there were no overlaps found, return true.
24    return true;
25}
26

Time and Space Complexity

Time Complexity

The time complexity of sorting the intervals is O(n log n), where n is the number of intervals in the input list.

After sorting, the code iterates over the sorted list just once to compare the start time of an interval with the end time of the previous interval using the pairwise function. This iteration is O(n).

Therefore, the overall time complexity is O(n log n + n) which simplifies to O(n log n) since the sorting part dominates the overall time complexity.

Space Complexity

The space complexity is O(n) if we take into account the space required for sorting the intervals, which usually requires temporary space proportional to the size of the list being sorted.

However, the use of pairwise in Python does not require additional space proportional to the number of intervals, as it generates pairs of consecutive items lazily. Thus, the additional space complexity due to pairwise is O(1).

So, the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]

["jm", "kn", "lo"]

["jklmnp"]

["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don’t know