46. Meeting Rooms

Problem Description

Given an array of meeting time intervals, determine if a person can attend all meetings without any overlaps. Each interval consists of a start time and an end time.

Example:

Input: intervals = [(0,30),(5,10),(15,20)]
Output: false
Explanation: 
The meetings (0,30) and (5,10) overlap, so it is impossible to attend all meetings.

Solution Code

import java.util.*;

/**
 * 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() == 0) {
            return true;
        }

        // Sort intervals based on start time
        intervals.sort((a, b) -> a.start - b.start);

        // Check for overlapping intervals
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals.get(i).start < intervals.get(i - 1).end) {
                return false;
            }
        }

        return true;
    }
}

Approach Name

Sorting and Linear Scan

Intuition

The problem requires checking if any two meetings overlap. If we sort the intervals based on their start times, we can easily check for overlaps by comparing the start time of the current meeting with the end time of the previous meeting. If the start time of the current meeting is less than the end time of the previous meeting, there is an overlap.

Algorithm

1. Sort Intervals:

   • Sort the intervals based on their start times.

2. Check for Overlaps:

   • Iterate through the sorted intervals and compare the start time of the current interval with the end time of the previous interval.
   • If the start time of the current interval is less than the end time of the previous interval, there is an overlap, and the person cannot attend all meetings.

3. Return Result:

   • If no overlaps are found, return true; otherwise, return false.

Complexity Analysis

• Time Complexity: O(n log n), where n is the number of intervals. Sorting the intervals takes O(n log n), and the linear scan takes O(n).
• Space Complexity: O(1), as we only use a constant amount of extra space for the sorting and comparison.

Leetcode Related Problems

1. Easy - 2848. Points That Intersect With Cars
2. Hard - 2402. Meeting Rooms III
3. Medium - 🔒 0253. Meeting Rooms II
4. Medium - 0056. Merge Intervals

GeeksForGeeks Related Problems

1. Easy - 701364. N meetings in one room
2. Easy - 876297. Meeting Rooms Related Articles: Meeting Rooms - Check if a Person Can Attend All Meetings

LintCode Related Problems

1. Easy - 0156. Merge Intervals
2. Medium - 0919. Meeting Rooms II