Python solution with detailed explanation


  • 0
    G

    Solution

    Meeting Rooms https://leetcode.com/problems/meeting-rooms/

    • Sort the input list of interval objects using key command in Python.
    • Invalid condition is when interval[i].start < interval[i-1].end i.e. next meeting will start before previous meeting will end.
    class Solution(object):
        def canAttendMeetings(self, intervals):
            """
            :type intervals: List[Interval]
            :rtype: bool
            """
            intervals.sort(key = lambda x: x.start)
            for i in range(1, len(intervals)):
                if intervals[i].start < intervals[i-1].end:
                    return False
            return True
    

    Editorial

    • The editorial solution has a brute force method where we compare every interval and test if they overlap. This is an O(N^2) solution.
    • Another interesting method to determine overlap:The earlier meeting ends before the later meeting begins. Therefore, the minimum end time of the two meetings (which is the end time of the earlier meeting) is smaller than or equal the maximum start time of the two meetings (which is the start time of the later meeting)
    private boolean overlap(Interval i1, Interval i2) 
    {
        return (Math.min(i1.end, i2.end) >Math.max(i1.start, i2.start));
    }
    

    Followup Problem


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.