Problem
You are given an array of meeting intervals, whereintervals[i] = [start, end] represents the start and end time of a meeting.
Return
true if a person can attend all meetings. Otherwise, return false. A person cannot attend two meetings that overlap in time.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
intervals = [[0,30],[5,10],[15,20]]Output
falseSolution
This problem can be solved using a Sorting approach.We first sort all meetings by their start time. After sorting, any overlapping meetings will appear next to each other.
We maintain the end time of the previous meeting. For every new meeting, if its start time is less than the previous meeting's end time, the meetings overlap and we return
false.
Otherwise, we update the end time to the end of the current meeting and continue checking the remaining meetings.
class Solution {
static boolean canAttend(int[][] arr) {
// Sort meetings by start time.
Arrays.sort(arr, Comparator.comparingInt(row -> row[0]));
int end = arr[0][1];
for (int i = 1; i < arr.length; i++) {
// Current meeting overlaps with the previous meeting.
if (arr[i][0] < end) {
return false;
}
// Update the end time.
end = arr[i][1];
}
return true;
}
}
Complexity
Sorting the meetings takesO(n log n) time, and checking the meetings takes O(n) time, resulting in O(n log n) overall time complexity.
Apart from the space used internally by sorting, only a constant number of variables is used, resulting in
O(1) extra space.