Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/252.html

 252.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.

 For example,
 Given [[0, 30],[5, 10],[15, 20]],
 return false.

 @tag-interval

Algorithm

To find whether there is an intersection of intervals, the easiest way is to compare every two intervals to see if there is an overlap. If so, just return false.

Compare whether there is overlap between the two intervals a and b, you can detect two cases,

• If the start position of a is greater than or equal to the start position of b, and the start position of a is less than the end position of b, there must be overlap,
• Another situation is that a and b exchange positions. If the start position of b is greater than or equal to the start position of a, and the start position of b is less than the end position of a, then there must be overlap

Code

Java

• Java
• C++
• Python

• import java.util.Arrays;
  
  public class Meeting_Rooms {
  
  
      public boolean canAttendMeetings(Interval[] intervals) {
  
          Arrays.sort(intervals, (a, b) -> a.start - b.start);
  
          for(int i = 0; i + 1 < intervals.length; i++){
  
              if(intervals[i].end > intervals[i + 1].start){
                  return false;
              }
          }
  
          return true;
      }
  }
  
  /*
      public class Interval {
          int start;
          int end;
          ...
      }
  */
  

• // OJ: https://leetcode.com/problems/meeting-rooms/
  // Time: O(NlogN)
  // Space: O(1)
  class Solution {
  public:
      bool canAttendMeetings(vector<Interval>& intervals) {
          sort(intervals.begin(), intervals.end(), [&](Interval &a, Interval &b) {
              return a.start < b.start;
          });
          for (int i = 1; i < intervals.size(); ++i) {
              if (intervals[i].start < intervals[i - 1].end) return false;
          }
          return true;
      }
  };
  

• class Solution:
      def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
          intervals.sort(key=lambda x: x[0])
          for i in range(len(intervals) - 1):
              if intervals[i][1] > intervals[i + 1][0]:
                  return False
          return True
  
  ############
  
  # Definition for an interval.
  # class Interval(object):
  #     def __init__(self, s=0, e=0):
  #         self.start = s
  #         self.end = e
  
  class Solution(object):
    def canAttendMeetings(self, intervals):
      """
      :type intervals: List[Interval]
      :rtype: bool
      """
      intervals = sorted(intervals, key=lambda x: x.start)
      for i in range(1, len(intervals)):
        if intervals[i].start < intervals[i - 1].end:
          return False
      return True
  
  

All Problems

All Solutions