Coding

Meeting Rooms

Asked at

Google

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an array of meeting time intervals where intervals[i] = [starti, endi].

Determine if a person could attend all meetings.

Input: intervals = [[1, 5], [3, 8], [6, 10], [12, 15]] Output: false Explanation: Overlapping meetings exist at [1,5] and [3,8], making it impossible to attend all.

Input: intervals = [[2, 6], [7, 9], [10, 14], [15, 18]] Output: true Explanation: No overlapping meetings, so all can be attended.

Input: intervals = [[0, 4], [4, 9], [10, 13], [14, 17]]

0 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti < endi <= 106

cpp

class Solution {
public:
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        // Your code goes here
    }
};

java

class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        // Your code goes here
    }
}

python

class Solution:
    def canAttendMeetings(self, intervals):
        # Your code goes here

javascript

class Solution {
    canAttendMeetings(intervals) {
        // Your code goes here
    }
}

csharp

public class Solution
{
    public bool canAttendMeetings(int[][] intervals)
    {
        // Your code goes here
    }
}

func canAttendMeetings(intervals [][]int) bool {
	// Your code goes here
}

Stuck? Show a way to structure it+

01Sort intervals by start time.
02Compare each start with the previous end.
03Reject on an overlap.
04Update the active end.
05Handle zero or one interval.

Reference answer

Sort meetings by start time. Once sorted, an overlap can only occur with the meeting that has the latest end among prior meetings; for non-overlapping sorted intervals, comparing to the immediately previous end is sufficient. Scan from the second interval and return false when current.start < previous.end; equality is allowed for half-open intervals, so a meeting ending at 10 can be followed by one starting at 10. Otherwise advance the previous end and continue. State that endpoint convention explicitly because it prevents off-by-one bugs. Sorting dominates at O(N log N) time, while the scan uses O(1) extra space apart from the sort. This is simpler and safer than checking every pair.

Then expect these follow-ups

How do you return a conflicting pair?
Tests: index preservation
Can a sweep-line solve this too?
Tests: alternative approaches

Hiring now

Google has 52 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Small Business Field Sales Representative
Denver, Colorado
Senior Technical Program Manager, Special Projects
Denver, Colorado; Lakewood, Colorado, United States
OSP Engineering Lead, Technical Operations
Denver, Colorado

Or practice this question first

Next question