algorithm - 为什么Leetcode的 "Meeting Rooms 2"数组要先排序？

Question

下面是Leetcode中的“Meeting Rooms 2”问题:

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.

我们都知道一个可能的解决方案是在比较相邻 session 的开始和结束时间之前对间隔数组进行排序。

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

但是假设我们有以下代码来检测两个 session 之间的时间冲突，

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

例如，我们有区间:[[15,20],[12,14],[1,17],[0,30],[7,10],[5,10] ]。以[15,20]开始， Room#1 的时间表应该是:[[7,10],[12,14],[15,20]]

现在它仍然是 [[1,17],[0,30],[5,10]]，他们都需要一个新房间， 2 号房间:[[1,17]]， 3 号房间:[[0,30]]， 4 号房间:[[5,10]]， 所以我们总共需要 4 个房间。

这是代码，

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

以上代码通过了 71/77 次测试，但在第 72 次测试失败。如果我们不首先对间隔进行排序，任何人都可以说出为什么它不起作用的原因？

Answer 1

您不需要对数组进行排序。它可以在 O(n) 时间复杂度内解决。这个想法是创建一个 count数组并用 +1 更新它在索引 start[i]和 -1在索引 end[i] . start和 end是 session 相应开始和结束时间的数组。

之后，你只需要添加所有+1和 -1并形成精确计数数组，然后返回该数组中存在的最大值。下面是伪代码:

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