JavaScript Algorithms: Meeting Rooms (LeetCode)

Photo by Benjamin Child on Unsplash

Description

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

Example 1:

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

Example 2:

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

Constraints:

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

Solution

I came up with a brute-force solution when I saw this question the first time. We can go through the intervals array and create a Set with all busy minutes. And if we see a minute that is already in Set we’re going to return false, otherwise return true.

Let’s look at examples:

Let’s try to implement it

So, according to the constraints, the time complexity is O(n * m), where n is the number of intervals and m is the difference between starti and endi. The space complexity is O(n) where n is the number of all differences between starti and endi.

Let’s think about how we can improve this algorithm. What if we sort it by starti in advance?

After that, we can check that each meeting ends before the new one starts:

The time complexity is O(nlogn) because of sort and space complexity is O(n).

I hope, it was useful for you. Thanks for reading! Looking forward to your feedback. See you soon ✌️