-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
음.. solve2 이상한거 아닌가요?
21.02.27 01:52 작성 조회수 93
1
[0, 30], [4, 9], [5, 15], [10, 16] 이런식으로 4개를 input 으로 할 경우.. 실제로는 강의실 3개면 되는데, solve2 로는 4개가 나오는거 같아요.
minHeap.peek() 만으로 intervals[i] 랑 비교를 해서 그런거 같은데.. 근본적으로 PQ 를 사용하면 안 되는거 아닌가 싶어요.
Q에 들어가는 값이 강의실별 선점된 시간일텐데.. intervals 를 for 돌리면서 바로 강의실 별 선점 시간을 지워버리면.. [10, 16] 처럼 직전이 아닌 이전 강의실에 할당 할 수 있는 경우는 대응이 안 될거 같아요.
답변을 작성해보세요.
0
0
푸샵맨 코딩스터디
지식공유자2021.02.28
안녕하세요. ~~
solve2도 잘 됩니다. 어제는 급하게 해봐서 그런지 주신 파라미터를 잘 못 넣은거 같은데요.
지금 잘됩니다.
질문주신 내용 중:
[10, 16] 처럼 직전이 아닌 이전 강의실에 할당 할 수 있는 경우는 대응이 안 될거 같아요.
=> PriorityQueue를 minHeap으로 가져갔기때문에 최상위에는 제일 작은값이 존재합니다.
[10, 16]을 만날때 minHeap 최상단에 end 타임 9 가 있습니다.
minHeap.peek().end <= intervals[i].start 이조건에 걸려서 9 < 10
minHeap에서 9를 빼버리고 [10, 16]을 넣습니다. 그래서 총3개가 됩니다.
=======solve2 소스코드==============
public int solve(Interval[] intervals) {
if (intervals == null || intervals.length == 0)
return 0;
Arrays.sort(intervals, (Interval a, Interval b) -> a.start - b.start);
int max = 0;
Queue<Interval> minHeap = new PriorityQueue<>((Interval a, Interval b) -> a.end - b.end);
for (int i = 0; i < intervals.length; i++) {
while (!minHeap.isEmpty() && minHeap.peek().end <= intervals[i].start) {
minHeap.poll();
}
minHeap.offer(intervals[i]);
max = Math.max(max, minHeap.size());
}
return max;
}
0
푸샵맨 코딩스터디
지식공유자2021.02.27
안녕하세요~
네 지금 보니까 solve2는 결과값이 안나오네요..
solve1 방식으로 금일 영상 재업데이트 하겠습니다.
비교 분석해서 올리도록하겠습니다.
감사합니다~
답변 3