252. Meeting Rooms

Description

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

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: intervals = [[0, 30], [5, 10], [15, 20]]

Output: false

Example 2

Input: intervals = [[7, 10], [2, 4]]

Output: true

Solutions

Solution 1

/**
 * 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]));
  }
}

Solution 2

/**
 * 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;
    }
}

Solution 3

/**
 * 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;
    }
}

Follow up