Can anyone explain why the array need to be sorted first?


  • 0
    H

    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.

    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);
            }
    

    Then we can work without sorting. I mean pick no matter which meeting, than group as many meetings without time conflict together as possible.

    Let's say 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?


Log in to reply
 

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