TIC
The Interns Company

Meeting Rooms

EasyAcceptance: 57.1%
ArraySorting

Problem Statement

Given an array of meeting time intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings. In other words, check if there are any overlapping intervals.

Constraints:

  • 0 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= starti < endi <= 10^6

Input Format:

  • An array of intervals representing meeting times

Output Format:

  • Return true if a person can attend all meetings (no overlapping intervals), otherwise return false

Examples:

Example 1:

Input:

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

Output:

false

Explanation:

The meeting intervals [0,30] and [5,10] overlap, so a person cannot attend both meetings.

Example 2:

Input:

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

Output:

true

Explanation:

The meeting intervals [7,10] and [2,4] do not overlap, so a person can attend both meetings.

Example 3:

Input:

intervals = [[1,2],[2,3]]

Output:

true

Explanation:

These meetings occur back-to-back, but they don't overlap. A meeting that ends at time 2 and another that starts at time 2 are not considered overlapping.

Solutions

Sort and Check Adjacent Intervals

Time: O(n log n) due to sorting
Space: O(1) or O(n) depending on the sorting implementation

Sort the intervals by start time, then check if any meeting ends after the next one starts.

Separate Start and End Times

Time: O(n log n) due to sorting
Space: O(n) for storing separate start and end arrays

An alternative approach where we separate the start and end times, then sort and check for overlaps.

Algorithm Walkthrough

Example input: nums = []

Step-by-step execution:

  1. Sort intervals by start time: [[0, 30], [5, 10], [15, 20]]
  2. Check if intervals[0][1] > intervals[1][0]: 30 > 5? Yes
  3. Found an overlap, return false

Hints

Hint 1
How would sorting the intervals make the problem easier?
Hint 2
After sorting, you only need to check if any meeting ends after the next one starts.
Hint 3
Be careful with the definition of overlap: [1,2] and [2,3] are not considered overlapping.

Video Tutorial

Meeting Rooms - Sorting Intervals

YouTube•Learn the Meeting Rooms solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize the meeting intervals on a timeline to identify overlaps.

Key visualization elements:

  • sorted intervals
  • overlapping pairs

Similar Questions

Insert Interval

Medium

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval. Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary). Return intervals after the insertion.

Meeting Rooms II

Medium

Given an array of meeting time intervals where intervals[i] = [starti, endi], find the minimum number of conference rooms required to hold all meetings.

Merge Intervals

Medium

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Non-overlapping Intervals

Medium

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Asked By

AmazonFacebookMicrosoftGoogleBloombergApple

Implementation Notes

This is a classic interval scheduling problem. The key insight is that if two meetings overlap, they cannot both be attended by one person. Sorting simplifies the problem by allowing us to check only adjacent intervals.