java - 为什么以下测试用例的代码输出为 3？

Question

我的编码问题与计算给定调度时间的最小房间数

给定由开始和结束时间 [[s1,e1],[s2,e2],...] (si < ei) 组成的 session 时间间隔数组，找到所需的最小 session 室数量。例子示例1输入:间隔 = [(0,30),(5,10),(15,20)]输出:2解释:我们需要两个 session 室房间 1:(0,30)房间2:(5,10),(15,20)例2输入:间隔 = [(2,7)]输出:1解释:只需要一间 session 室

这是我正在尝试解决的测试用例:[(65,424),(351,507),(314,807),(387,722),(19,797),(259,722),(165,221)]

输出应该是 6，但我的代码返回 3，我不知道为什么。

当我运行这个测试用例 [(65,424),(351,507),(314,807),(387,722),(19,797),(259,722)] 时，我的解决方案会打印 6，但是，只要我添加 (165,221 )，解决方案打印 3。

``代码如下:

/**
 *Definition of Interval:
 * public classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */

public class Solution {
    /**
     * @param intervals: an array of meeting time intervals
     * @return: the minimum number of conference rooms required
     */

public int minMeetingRooms(List<Interval> intervals) {
        // Write your code here
        if(intervals.size() == 0 || intervals == null) {
            return 0;
        }

        Interval[] interArr = new Interval[intervals.size()];
        interArr = intervals.toArray(interArr);
        Arrays.sort(interArr, (a,b) -> a.start - b.start);
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.add(interArr[0].end);
        for(int i = 1; i < interArr.length; i++) {
            Interval curr = interArr[i];
            if (curr.start < pq.peek()) {
                pq.add(interArr[i].end);
            }
        }
        return pq.size();
    }
}

``

Answer 1

我经常用这个作为面试问题。

简单地说，您的输出不正确因为您的算法不正确。您基本上已经编写了一个测试用例，证明您的算法是不正确的。

提示，您不需要优先级队列。问题比你想象的要简单。