Java

Question

这是我对 leetcode 759.Employee Free Time 的解决方案，但它有索引越界问题，我不明白。

我收到“索引 0 超出长度 0 范围”异常。

public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
    PriorityQueue<List<Interval>> pq = new PriorityQueue<>((a, b) -> {
        System.out.println("b start " + b.get(0).start + "  end " + b.get(0).end);
        System.out.println("a start " + a.get(0).start + "  end " + a.get(0).end);
        Interval first = a.get(0);
        Interval second = b.get(0);
        int diff = first.start - second.start;
        if (diff == 0) return second.end - first.end;
        return diff;
    });
    for (List<Interval> s: schedule) pq.add(s);
    
    List<Interval> rst = new ArrayList<>();
    int start = pq.peek().get(0).start, end = pq.peek().get(0).end;
    while (!pq.isEmpty()) {
        List<Interval> list = pq.poll();
        Interval currt = list.remove(0);
        if (start <= currt.end) end = Math.max(end, currt.end);
        else {
            Interval freeTime = new Interval(end, currt.start);
            rst.add(freeTime);
            start = currt.start;
            end = currt.end;
        }
        pq.add(list);
    }
    return rst;
}

我使用的测试用例是'[[[1,2]],[[1,3]],[[4,10]]]'，这是输出：

b start 1  end 2
a start 1  end 3
b start 1  end 3
a start 4  end 10
b start 1  end 2
a start 4  end 10
b start 1  end 2

我只有 3 个列表，根据输出结果，它似乎已经比较了所有列表。为什么 PriorityQueue 再次将 [1,2] 与空列表进行比较？

Answer 1

您正在从 pq 进行轮询并删除第 0 个元素。

List<Interval> list = pq.poll();
Interval currt = list.remove(0); //here

你再次将这个完全相同的列表添加到 pq。

pq.add(list);

所以当添加到 pq 时，pq 的比较器启动并看到第 0 个元素被删除的列表。

这就是它抛出错误的原因。

Java - 使用 PriorityQueue 排序列表但列表为空

Java - Use PriorityQueue sort list but have empty list

priority-queue