Meeting Rooms

Question 1 (LC.252)

Given an array of time intervals, determine if there's no overlap.

Example

I: [[0,30],[5,10],[15,20]]
O: false

I: [[7,10],[2,4]]
O: true

Approach

An overlap can happen when the start time of the next meeting is before the end time of the current meeting. Sort by the start time. Check if the current meeting start time collides with the end time in the previous meeting.

Code

public boolean canAttendMeetings(Interval[] meetings) {
    // edge check
    if (meetings == null || meetings.length <= 1) {
        return true;
    }
    // sort by start time
    Arrays.sort(meetings, (Interval i1, Interval i2) -> i1.start - i2.start); 
    // check schedule conflict
    for (int i = 1; i < meetings.length; i++) {
        if (meetings[i].start < meetings[i-1].end) {
            return false;
        }
    }
    return true;
}

Complexity

Time O(nlogn) Space O(1)

Question 2 (LC.253)

Given a list of time intervals [[start_i, end_i], ..., [start_n, end_n]], find the minimum number of conferences rooms to hold all the meetings.

Example

I: [[0, 30],[5, 10],[15, 20]]
O: 3

I: [[7,10],[2,4]]
O: 1

Notice the input is not sorted.

Sweep Line

We can visualize this question as the picture below.

Intuitively, we want to somehow sort the meetings and find the maximum number of overlaps at some point. The line-sweep algorithm is designed to find intersections between intervals (1D) or rectangles (2D). A brute force attempt would be to scan the entire timeline in some unit of time (i.e. in minutes) and check the overlapping of meetings at each point of time. But O(number of minutes) is very expensive.

Is there any way to reduce the computational complexity? We don't have to scan the time frame between two events (i.e. start of a meeting, start of another meeting). Because in that time frame, the number of conference rooms stay the same. In fact, the start and the end of a meeting are the only two events that count. Therefore, we can scan these two types of events instead of the entire timeline.

If we visualize a vertical line that sweeps from left to right, at each event, the intersection count will increase by 1 when the line encounters the start of an interval and decrease by 1 when the line encounters the end of an interval. The sorting order will be ascending in time regardless of the type of the event nor the name of the meeting.

Approach

Step 1
Create the list of events from the list of meetings

Step 2
Sort the list of events

Step 3
Sweep (scan) the sorted list of events and count the number of intersections
Maintain a max count

Step 4
Return the max

Code

private class Event {
    int time;
    boolean isStart;
    Event(int time, boolean isStart) {
        this.time = time;
        this.isStart = isStart;
    }
}

public int minMeetingRooms(List<Interval> meetings) {
    // edge check
    if (meetings == null || meetings.size() == 0) {
        return 0;
    }
    // Step 1 Create a list of events
    List<Event> events = new ArrayList<>(); // meetings.size() * 2
    for (Interval meeting : meetings) {
        events.add(new Event(meeting.start, true));
        events.add(new Event(meeting.end, false));
    }
    // Step 2 Sort events
    Comparator<Event> eventComp = new Comparator<Event>(){
        // negative is less than, zero is equal, positive is greater than
        public int compare(Event e1, Event e2) {
            // we want to put the end time first so we don't increase the count
            if (e1.time == e2.time) {
                return Boolean.compare(e1.isStart, e2.isStart);
            } else {
                return e1.time - e2.time;
            }
        }
    };
    Collections.sort(events, eventComp);
    // Step 3 Sweep the sorted list of events
    int maxIntersections = 0;
    int intersections = 0;
    for (Event event : events) {
        if (event.isStart) {
            intersections++;
        } else {
            intersections--;
        }
        maxIntersections = Math.max(maxIntersections, intersections);
    }
    return maxIntersections;
}

# sweep line algo 
# scan from left to right 
# start and end time as events
# store in BST or even easier just a counter 

def minMeetingRooms(self, intervals: List[List[int]]) -> int:
    n = len(intervals)
    if n == 0:
        return 0
    
    events: List[Tuple[int, int]] = []
    for interval in intervals:
        events.append((interval[0], 1))
        events.append((interval[1], -1))
    
    # sort by meeting time then by event type 
    sorted_events = sorted(events)
    
    intersections = 0
    rooms = 0
    for event in sorted_events:
        intersections += event[1]
        rooms = max(rooms, intersections)
    
    return rooms 

Complexity

Time O(nlogn) + O(n) Space O(n)

Greedy Approach

Alternatively, we can try greedy since this is a minimization problem on a sequence.

First, we want to sort the meetings by start time (or symmetrically by end time). We can model each conference room as an interval that keeps a start time and an end time. We want to put the next meeting in the conference room with the smallest end time. If the smallest end time is bigger than the start time of next meeting, we need to create a new conference room.

One way to prove the optimality of a greedy algorithm is to show that at every step there is no better approach than making a greedy choice locally. We can induct on the number of conference rooms. Suppose $n^{th}$ conference needs to be created for the current meeting $[start_i, end_i]$. If we need to add a new conference room, then every existing conference room has a schedule conflict with the current meeting. We have $n-1$ meetings collide with the current meeting at time $start_i$. This is true because the meetings are sorted by their start time (i.e. a gap then a meeting later is not possible). Regardless of what strategies we use, at least we need $n$ conferences.

Code

public int minMeetingRooms(Interval[] meetings) {
    // edge check
    if (meetings == null || meetings.length == 0) {
        return 0;
    }
    // sort by starting time
    Arrays.sort(meetings, (Interval i1, Interval i2) -> i1.start - i2.start);
    // create a priority queue of conference room finish times
    PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
    minHeap.offer(meetings[0].end);
    for (int i = 1; i < meetings.length; i++) {
        // need an extra conference room
        if (minHeap.peek() > meetings[i].start) {
            minHeap.offer(meetings[i].end);
        } else { // can fit in an existing room
            minHeap.poll();
            minHeap.offer(meetings[i].end);
        }
    }
    return minHeap.size();
}

Question: What if interval with different sizes have the same starting time? (i.e. a long meeting and a short meeting both start at 10). We don't care because the starting time alone can guarantee the optimality of this greedy algorithm.

Note: In Java 8, Comparator is a functional interface. It can accept lambda expression for its compare method.

Complexity

Time O(nlogn) Space O(n)

Time Intersection Variant

A variant from Meeting Rooms II is to return all the intersection time between two lists of meetings. The brute force approach is still to scan the entire timeline and find overlaps. The better approach is to sweep the events (disregard which list they are from) and store the intervals that are intercepted (from 2 start events until the next end event).

References

• Top Coder Line Sweep Algorithm
• MIT 6.046 Recitation 6 Notes
• Oreilly What’s new in Java 8
• Java Doc Interface Comparator