252.meeting-rooms-i.md

252. Meeting Rooms

Problem

Given an array of meeting time intervals where intervals[i] = [start, end], 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 <= 10^4
• intervals[i].length == 2
• 0 <= starti < endi <= 10^6

Key Insight

If a person can attend all meetings, that means no two meetings overlap with each other. The two meetings can conflict if one starts before the previous one ends.

|-------|
    |-------|

Sorting

We can sort the intervals by the start time, we can process the earliest meeting first. Then check if any two meetings overlap with each other.

fun canAttendMeetings(intervals: Array<IntArray>): Boolean {
    intervals.sortBy { it[0] }
    for (i in 1 until intervals.size) {
        val previous = intervals[i - 1]
        val current = intervals[i]
        if (previous[1] > current[0]) return false
    }
    return true
}

• Time Complexity: O(n log n), where n is the number of intervals.
• Space Complexity: O(logn).

Line Sweep

We can use the difference array to restore the original array of all intervals, then check if there is more than one meeting at the same time.

[1, 5]
[0, 7]
[4, 8]

0, 1, 2, 3, 4, 5, 6, 7, 8, 9
   |-----------|
0  1  0  0  0  0 -1  0  0, 0

|--------------------|
1  1  0  0  0  0 -1  0 -1, 0

            |-----------|
1  1  0  0  1  0 -1  0 -1,-1

// Prefix sum of the difference array
1  2  2  2  3  3  2  2  1  0

fun canAttendMeetings(intervals: Array<IntArray>): Boolean {
    if (intervals.isEmpty()) return true
    val min = intervals.minOf { it[0] }
    val max = intervals.maxOf { it[1] }
    val diff = IntArray(max - min + 2)
    for ((start, end) in intervals) {
        diff[start - min]++
        diff[end - min + 1]--
    }
    var value = 0
    for (i in diff.indices) {
        value += diff[i]
        if (value > 1) return false
    }
    return true
}

• Time Complexity: O(n + k), where n is the number of intervals and k is the range of the intervals.
• Space Complexity: O(k), where k is the range of the intervals.