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. Sinceintervals
consists of sub-lists where each sub-list represents a meeting time interval[start, end]
, thesort()
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'sitertools
is used to create an iterator that will return tuples containing pairs of consecutive elements (or intervals in this case). This means if the sortedintervals
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 expressionall(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 functionall
will returnTrue
only if every evaluation within the expression yieldsTrue
, 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 yieldFalse
, and thus theall
function will short-circuit and returnFalse
. -
Returning the result: The boolean result from the
all
function is returned directly. If the result isTrue
, it means all the meetings do not overlap, and the individual can attend them all. If the result isFalse
, 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 EvaluatorExample 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'sitertools
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 theall
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 meeting30
is not less than the start time of the second meeting5
, the conditiona[1] <= b[0]
isFalse
. Therefore, theall
function would returnFalse
. -
Because
all
short-circuits (stops evaluating) as soon as it encounters aFalse
, 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.
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
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!