252.Meeting Rooms

Tags: [queue], [interval], [merge]

Com: {fb}

Link: https://leetcode.com/problems/meeting-rooms/\#/description

Given an array of meeting time intervals consisting of start and end times[[s1,e1],[s2,e2],...](si< ei), determine if a person could attend all meetings.

For example,
Given[[0, 30],[5, 10],[15, 20]],
returnfalse.

Solution: Sort

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

from collections import deque

class Solution(object):
    def canAttendMeetings(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: bool
        """
        if not intervals:
            return True

        intervals.sort(key=lambda x: x.start)
        for i in xrange(len(intervals) - 1):
            interval1 = intervals[i]
            interval2 = intervals[i + 1]
            if interval1.end > interval2.start:
                return False

        return True

Revelation:

• There exists one case: [[1, 100], [2, 3], [4, 5], [6, 7]]. The above algorithm still can get the correct result for this case. Because once we find two intervals which can be merged, we return False directly.

Note:

• Time complexity = O(nlgn), n is the number of intervals.
• Space complexity = O(1).

Solution: Sort, Queue

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

from collections import deque

class Solution(object):
    def canAttendMeetings(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: bool
        """
        if not intervals:
            return True

        intervals.sort(key=lambda x: x.start)
        queue = deque()
        for interval in intervals:
            if not queue or not self.can_merge(queue[-1], interval):
                queue.append(interval)
            else:
                last_interval = queue[-1]
                last_interval.end = max(last_interval.end, interval.end)

        return len(queue) == len(intervals)

    def can_merge(self, interval1, interval2):
        return interval1.end > interval2.start

Revelation:

• If interval1.end == interval2.start, leetcode think these two intervals should be merged.

Note:

• Time complexity = O(nlgn), n is the number of intervals.
• Space complexity = O(n), n is the number of intervals.