CODEWITHSUNDEEP
algorithm
shen
shen

Reputation: 1051

Why the array need to be sorted first in "Meeting Rooms 2" of Leetcode?

The following is the problem "Meeting Rooms 2" in Leetcode:

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.

As we all know a possible solution is to sort the interval array before compare the start and the end time of the adjacent meeting.

    public int minMeetingRooms(Interval[] intervals) {
        Arrays.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval a, Interval b) {
                return a.start - b.start;
            }
        });
        List<Interval> list = new ArrayList<>(Arrays.asList(intervals));
        int count = 0;
        while (!list.isEmpty()) {
            int end = list.remove(0).end; count++; // create new timeline
            Iterator<Interval> ite = list.iterator();
            while (ite.hasNext()) {
                Interval next = ite.next();
                if (next.start >= end) { // add to current timeline
                    end = next.end;
                    ite.remove();
                }
            }
        }
        return count;
    }

But let's say we have the following code to detect the time conflict between two meetings,

    private boolean isConflict(Interval a, Interval b) {
        boolean abfb = (a.start < b.start && a.end <= b.start);
        boolean aaftb = (b.start < a.start && b.end <= a.start);
        return !(abfb || aaftb);
    }

For example, we have the intervals: [[15,20],[12,14],[1,17],[0,30],[7,10],[5,10]]. Begin with [15,20], The schedule of Room#1 should be: [[7,10],[12,14],[15,20]]

Now it remains [[1,17],[0,30],[5,10]], they all need a new room, Room#2 : [[1,17]], Room#3 : [[0,30]], Room#4 : [[5,10]], So we need 4 rooms in all.

And here is the code,

    public int minMeetingRooms(Interval[] intervals) {
        List<Interval> list = new LinkedList<>(Arrays.asList(intervals));
        int count = 0;
        while (!list.isEmpty()) {
            List<Interval> group = new ArrayList<>();
            group.add(list.remove(0)); count++;
            Iterator<Interval> ite = list.iterator();
            while (ite.hasNext()) {
                Interval noGroup = ite.next();
                boolean conflict = false;
                for (Interval inGroup : group) {
                    if (isConflict(inGroup,noGroup)) { conflict = true; break; }
                }
                if (!conflict) {
                    group.add(noGroup);
                    ite.remove();
                }
            }
        }
        return count;
    }

The above code passed 71/77 tests, but failed on the 72th. Any one can tell the reason why it doesn't work if we do not sort first the intervals?

Upvotes: 0

Views: 2425

Answers (2)

CodeHunter
CodeHunter

Reputation: 2082

You need not to sort the array. It can be solved in O(n) time complexity. The idea is to create a count array and update it with +1 at index start[i] and with -1 at index end[i]. start and end are the arrays of corresponding start and end timings of the meetings.

After that, you just need to add all +1 and -1 and form the exact count array and then return the maximum value present in that array. Below is the pseudo code:

int[] count = new int[100];
for(int i=0;i<start.length;i++){
    count[start[i]] += 1;
    count[end[i]] -= 1;
}
//form the count array with exact values in this loop
count[0] = 0;
for(int i =0;i<count.length;i++){
    count[i] = count[i] + count[i-1];
}
return max(count);

Upvotes: 3

Prune
Prune

Reputation: 77860

Your "greedy" algorithm will not make optimal use of rooms for some input sets. It accepts the first fit it finds in the list of intervals. Rather, it needs to take the closest fit for every available opening. One way to achieve this is to sort the intervals by starting time; that way, it will always find the earliest available meeting once the most recent one is completed.

For instance, generate several sets of meetings with 1-unit gaps: say, 3, 4, 5, and 6 units long.

[[1, 3], [4, 6], [7, 9], ...]
[[1, 4], [5, 8], [9, 12], ...]
[[1, 5], [6, 10], [11, 15], ...]
[[1, 6], [7, 12], [13, 18], ...]

Feed them to your algorithm in order, and you'll get the optimal 4 rooms. Shuffle them randomly, and you'll require 5 or 6 rooms.

Upvotes: 1

Related Questions