Solution For Meeting Rooms

The Meeting Rooms problem on LeetCode requires us to determine if a set of meeting times overlaps.

The problem can be described in this way:

Given an array of meeting time intervals where intervals[i] = [start_i, end_i], determine if a person could attend all meetings.

Example:

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

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

We can solve this problem using a greedy approach. We can sort the intervals based on their start times, and then iterate over the sorted array, checking if the current interval overlaps with the previous interval. If there is an overlap, we return False, since it’s not possible to attend both meetings. If there is no overlap, we continue iterating.

Here’s the Python implementation:

python
def canAttendMeetings(intervals):
intervals.sort(key=lambda x: x[0])
for i in range(1, len(intervals)):
if intervals[i][0] < intervals[i-1][1]:
# There is an overlap
return False
return True

We start by sorting the intervals based on their start times:

python
intervals.sort(key=lambda x: x[0])

Then, we iterate over the sorted intervals, checking for overlaps:

python
for i in range(1, len(intervals)):
if intervals[i][0] < intervals[i-1][1]:
# There is an overlap
return False

If there is an overlap, we return False. If there is no overlap, we continue iterating. If we reach the end of the array without finding an overlap, we return True:

python
return True

The time complexity of this algorithm is O(n log n) because of the sorting, and the space complexity is O(1) because we are not using any additional data structures.

Step by Step Implementation For Meeting Rooms

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    public boolean canAttendMeetings(Interval[] intervals) {
        // sort the intervals by start time
        Arrays.sort(intervals, new Comparator() { 
            public int compare(Interval i1, Interval i2) { 
                return i1.start - i2.start;
            } 
        });
        
        // check for overlapping intervals
        for (int i = 0; i < intervals.length - 1; i++) {
            if (intervals[i].end > intervals[i + 1].start) {
                return false;
            }
        }
        
        return true;
    }
}

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

def canAttendMeetings(intervals):
    # Sort the intervals by start time
    intervals.sort(key=lambda x: x[0])
    
    # Check for overlapping meetings
    for i in range(1, len(intervals)):
        if intervals[i][0] < intervals[i - 1][1]:
            return False
        
    return True

var canAttendMeetings = function(intervals) {
    // sort the intervals by start time
    intervals.sort((a, b) => a.start - b.start);
    
    // check for overlapping intervals
    for (let i = 0; i < intervals.length - 1; i++) {
        if (intervals[i].end > intervals[i + 1].start) {
            return false;
        }
    }
    
    return true;
};

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    bool canAttendMeetings(vector& intervals) {
        // check for empty input
        if (intervals.empty()) {
            return true;
        }
        
        // sort the intervals by start time
        sort(intervals.begin(), intervals.end(), 
             [](const Interval& i1, const Interval& i2) {
                 return i1.start < i2.start;
             });
        
        // check for overlapping intervals
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i].start < intervals[i-1].end) {
                return false;
            }
        }
        
        return true;
    }
};

using System; 
using System.Collections.Generic; 

public class Solution { 

public bool CanAttendMeetings(int[][] intervals) { 

// sort the intervals by start time 

Array.Sort(intervals, (a, b) => a[0] - b[0]); 

for (int i = 0; i < intervals.Length - 1; i++) { 

// if there is an overlap, then the person cannot attend all meetings 

if (intervals[i][1] > intervals[i + 1][0]) { 

return false; 

} 

} 

// if no overlaps were found, then the person can attend all meetings 

return true; 

} 

}