252. Meeting Rooms
https://leetcode.com/problems/meeting-rooms/
---
Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.
Example 1:
Input: [[0,30],[5,10],[15,20]]
Output: false
Example 2:
Input: [[7,10],[2,4]] Output: true
Related problems
---
Intuition
Check for overlaps, if overlap => false
To check for overlaps, we need to pick one way of ordering rooms
Sort by start time or end time ascending - doesn't matter which time
If start time of current < end time of previous => overlap => return false
---
Time - O(N log N)
Space - O(1)
---
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Definition of Interval: | |
| * public class Interval { | |
| * int start, end; | |
| * Interval(int start, int end) { | |
| * this.start = start; | |
| * this.end = end; | |
| * } | |
| * } | |
| */ | |
| public class Solution { | |
| /** | |
| * @param intervals: an array of meeting time intervals | |
| * @return: if a person could attend all meetings | |
| */ | |
| public boolean canAttendMeetings(List<Interval> intervals) { | |
| if (intervals == null || intervals.size() <= 1) { | |
| return true; | |
| } | |
| Collections.sort(intervals, (a, b) -> Integer.compare(a.start - b.start)); | |
| for (int i = 1; i < intervals.size(); i++) { | |
| if (intervals.get(i).start < intervals.get(i - 1).end) { | |
| return false; | |
| } | |
| } | |
| return true; | |
| } | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Definition of Interval: | |
| * public class Interval { | |
| * int start, end; | |
| * Interval(int start, int end) { | |
| * this.start = start; | |
| * this.end = end; | |
| * } | |
| * } | |
| */ | |
| public class Solution { | |
| /** | |
| * @param intervals: an array of meeting time intervals | |
| * @return: if a person could attend all meetings | |
| */ | |
| public boolean canAttendMeetings(List<Interval> intervals) { | |
| if (intervals == null || intervals.size() <= 1) { | |
| return true; | |
| } | |
| Collections.sort(intervals, (a, b) -> Integer.compare(a.end, b.end)); | |
| for (int i = 1; i < intervals.size(); i++) { | |
| if (intervals.get(i).start < intervals.get(i - 1).end) { | |
| return false; | |
| } | |
| } | |
| return true; | |
| } | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution: | |
| def canAttendMeetings(self, intervals: List[List[int]]) -> bool: | |
| intervals = sorted(intervals) | |
| for i in range(1, len(intervals)): | |
| if intervals[i][0] < intervals[i - 1][1]: | |
| return False | |
| return True |
