Java – Use PriorityQueue sort list but have empty list

This is my solution for leetcode 759. Employee Free Time, but it has index out of boundary issue that i don’t understand.

I got “index 0 out of bounds for length 0” exception.

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

The test case i used is ‘[[[1,2]],[[1,3]],[[4,10]]]’ and this is the output:

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

I only have 3 lists and based on the output, it looks like it has compared all lists. Why does PriorityQueue compare [1,2] again with an empty list?

Answer

you are polling from pq and removing the 0th element.

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

you again adding this very same list to pq.

pq.add(list);

so when adding to pq, pq’s comparator kicks in and see a list with 0th element removed.

thats why its throwing error.

Advertisement

Answer