Saturday, March 12, 2016

Leetcode meeting room ||


Wednesday, August 19, 2015

Leetcode: Meeting Rooms II 

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.
For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.


Understand the problem:
A similar problem can be found:
http://buttercola.blogspot.com/2014/11/facebook-maximum-number-of-overlapping.html

The problem can be also transformed as max number of overlaps. 

Code (Java):
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        if (intervals == null || intervals.length == 0) {
            return 0;
        }
         
        int len = intervals.length;
        int[] startTime = new int[len];
        int[] endTime = new int[len];
         
        for (int i = 0; i < len; i++) {
            Interval curr = intervals[i];
            startTime[i] = curr.start;
            endTime[i] = curr.end;
        }
         
        // Sort the start and end time
        Arrays.sort(startTime);
        Arrays.sort(endTime);
         
        int activeMeetings = 0;
        int numMeetingRooms = 0;
         
        int i = 0;
        int j = 0;
         
        while (i < len && j < len) {
            if (startTime[i] < endTime[j]) {
                activeMeetings++;
                numMeetingRooms = Math.max(numMeetingRooms, activeMeetings);
                i++;
            } else {
                activeMeetings--;
                j++;
            }
        }
         
        return numMeetingRooms;
    }
}

Analysis:
Sorting two arrays take O(nlogn) time. Compare takes O(n) time. So the overall time complexity is still bounded by O(nlogn). 

An alternative solution using Priority Queue:
An alternative solution is to use a priority queue to store the end times. Then we sort the intervals according to its start time. We iterate through the intervals. If the current start time is less than the earliest end time in the pq, numRooms++. Else, remove the earliest time from the pq. For each iteration, we also need to offer the current ending time into the pq. 

Code (Java):
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        if (intervals == null || intervals.length == 0) {
            return 0;
        }
         
        Arrays.sort(intervals, new IntervalComparator());
         
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int numRooms = 1;
         
        pq.offer(intervals[0].end);
         
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i].start < pq.peek()) {
                numRooms++;
                pq.offer(intervals[i].end);
            } else {
                pq.poll();
                pq.offer(intervals[i].end);
            }
        }
         
        return numRooms;
         
    }
     
    public class IntervalComparator implements Comparator<Interval> {
        @Override
        public int compare(Interval a, Interval b) {
            return a.start - b.start;
        }
    }
}


Posted by at  
Labels: , 

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)