Given an array of meeting time intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings.
Constraints
0 <= intervals.length <= 104
intervals.length == 2
0 <= starti < endi <= 106
Approach
Links
GeeksforGeeks
ProgramCreek
YouTube
Examples
Input: intervals = [[0, 30], [5, 10], [15, 20]]
Output: false
Input: intervals = [[7, 10], [2, 4]]
Output: true
Solutions
/**
* Time complexity : O(N*N)
* Space complexity : O(1)
*/
class Solution {
public boolean canAttendMeetings(int[][] intervals) {
for (int i = 0; i < intervals.length; i++) {
for (int j = i + 1; j < intervals.length; j++) {
if (overlap(intervals[i], intervals[j]))
return false;
}
}
return true;
}
public static boolean overlap(int[] i1, int[] i2) {
return ((i1[0] >= i2[0] && i1[0] < i2[1]) ||
(i2[0] >= i1[0] && i2[0] < i1[1]));
}
}
/**
* Time complexity :
* Space complexity :
*/
class Solution {
public boolean canAttendMeetings(int[][] intervals) {
if(intervals == null || intervals.length == 0) {
return true;
}
Arrays.sort(intervals, (a, b) -> a[0]-b[0]);
int endTime = intervals[0][1];
for(int i = 1; i < intervals.length; i++) {
if(intervals[i][0] < endTime) {
return false;
}
if(intervals[i][1] > endTime) {
endTime = intervals[i][1];
}
}
return true;
}
}
/**
* Time complexity : O(nlogn). The time complexity is dominated by sorting.
* Once the array has been sorted, only O(n) time is taken to go through
* the array and determine if there is any overlap.
* Space complexity : O(1). Since no additional space is allocated.
*/
class Solution {
public boolean canAttendMeetings(int[][] intervals) {
if(intervals == null || intervals.length == 0) {
return true;
}
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;
}
}