Почему вывод этого кода 3 для приведенного ниже теста? - PullRequest
Новая
       40

Почему вывод этого кода 3 для приведенного ниже теста?

0 голосов
/ 12 марта 2020

Мой вопрос о кодировании связан с подсчетом минимального количества комнат с учетом времени планирования

С учетом массива временных интервалов встречи, состоящих из времени начала и окончания [[s1, e1], [s2, e2] , ...] (si

Это тестовый пример, который я пытаюсь решить: [(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();
    }
}

``

1 Ответ

0 голосов
/ 12 марта 2020

Я часто использую это как вопрос для интервью.

Проще говоря, ваш вывод неправильный , потому что ваш алгоритм неверен. Вы в основном написали тестовый пример, который демонстрирует ваш алгоритм неверен.

Подсказка, вам не нужна очередь с приоритетами. Проблема проще, чем вы думаете.

...