Problem:
Given an array of meeting time intervals (start time , end time) find if all the meetings could be attended.
For example,
Given the input array of intervals:
[[10,20],[15,30],[30,40]]
Return false because the meetings [10,20] and [15,30] overlap.
For the intervals
[[10,30],[40,50]]
Return true because the meetings don’t overlap
Try out the solution here:
https://leetcode.com/problems/meeting-rooms/
Solution:
Hint:
- Sort the array of intervals by start time
The solution is straightforward
First sort the array by start time
Then compare the end time and start time of consecutive intervals.
If any of them overlap return false , else return true
ALGORITHM:
STEP 1: If interval size is 0 , return true
STEP 2: Sort the array based on start time
STEP 3: Iterate through the array and check if any of the intervals overlap (end of previous interval greater than start of current interval) .If so return false
STEP 4: Return true
Code:
class Solution {
public boolean canAttendMeetings(int[][] intervals) {
if(intervals.length ==0) return true;
Arrays.sort(intervals,(a,b) -> Integer.compare(a[0],b[0]));
for(int i=0;i<intervals.length-1;i++){
if(intervals[i][1] > intervals[i+1][0]){
return false;
}
}
return true;
}
}
Time complexity: O(nlogn) for the initial sorting plus the single iteration through the array
Space complexity: O(1) since there is no storage used in proportion to the input.
That’s it!
Leave a Reply