Description
Given an array of meeting time intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings.
Example 1:
Input: intervals = [[0,30],[5,10],[15,20]]
Output: false
Example 2:
Input: intervals = [[7,10],[2,4]]
Output: true
Constraints:
0 <= intervals.length <= 104intervals[i].length == 20 <= starti < endi <= 106
Solutions
Solution 1: Sorting
We sort the meetings based on their start times, and then iterate through the sorted meetings. If the start time of the current meeting is less than the end time of the previous meeting, it indicates that there is an overlap between the two meetings, and we return false. Otherwise, we continue iterating.
If no overlap is found by the end of the iteration, we return true.
The time complexity is O(n × log n), and the space complexity is O(log n), where n is the number of meetings.
PythonJavaC++GoTypeScriptRust
class Solution:
def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
intervals.sort()
return all(a[1] <= b[0] for a, b in pairwise(intervals))(code-box)
class Solution {
public boolean canAttendMeetings(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
for (int i = 1; i < intervals.length; ++i) {
if (intervals[i - 1][1] > intervals[i][0]) {
return false;
}
}
return true;
}
}(code-box)
class Solution {
public:
bool canAttendMeetings(vector<vector<int>>& intervals) {
ranges::sort(intervals, [](const auto& a, const auto& b) {
return a[0] < b[0];
});
for (int i = 1; i < intervals.size(); ++i) {
if (intervals[i - 1][1] > intervals[i][0]) {
return false;
}
}
return true;
}
};(code-box)
func canAttendMeetings(intervals [][]int) bool {
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][0] < intervals[j][0]
})
for i := 1; i < len(intervals); i++ {
if intervals[i][0] < intervals[i-1][1] {
return false
}
}
return true
}(code-box)
function canAttendMeetings(intervals: number[][]): boolean {
intervals.sort((a, b) => a[0] - b[0]);
for (let i = 1; i < intervals.length; ++i) {
if (intervals[i][0] < intervals[i - 1][1]) {
return false;
}
}
return true;
}(code-box)
impl Solution {
pub fn can_attend_meetings(mut intervals: Vec<Vec<i32>>) -> bool {
intervals.sort_by(|a, b| a[0].cmp(&b[0]));
for i in 1..intervals.len() {
if intervals[i - 1][1] > intervals[i][0] {
return false;
}
}
true
}
}(code-box)
