-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
MeetingRoom2 질문드립니다.
21.03.11 22:36 작성 조회수 76
2
안녕하세요. 강사님.
미팅룸2 강의 내용 질문드립니다.
특정 케이스 에서 PrioryQueue 의 사이즈가 '실제 사이즈 -1' 된 값으로 리턴되는 현상이 발생하더라구요..
혹시 왜 그런지 알 수 있을까요?
소스코드도 같이 첨부합니다.
package CH1_StringArray;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;
/*
class Interval {
int start;
int end;
Interval() {
start = 0;
end = 0;
}
Interval(int s, int e) {
start = s;
end = e;
}
}
*/
public class T6_MeetingRoom2 {
/*
Given an array of meeting time intervals consisting of start and end
times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of
conference rooms required.
Input: [[0,30],[5,10],[15,20]]
Output: 2
Input: [[7,10],[2,4]]
Output: 1
*/
public static void main(String[] args) {
// 2 -> 2, true
// Interval in1 = new Interval(0, 30);
// Interval in2 = new Interval(4, 9);
// Interval in3 = new Interval(5, 15);
// Interval in4 = new Interval(10, 16);
// Interval[] intervals = {in1, in2, in3, in4};
// 1 -> 0, False
// Interval in1 = new Interval(7, 10);
// Interval in2 = new Interval(2, 4);
// Interval[] intervals = {in1, in2};
// 2 -> 1, False
Interval in1 = new Interval(0, 30);
Interval in2 = new Interval(5, 10);
Interval in3 = new Interval(15, 20);
Interval[] intervals = {in1, in2, in3};
T6_MeetingRoom2 a = new T6_MeetingRoom2();
System.out.println(a.solve(intervals));
}
public int solve(Interval[] intervals) {
if(intervals == null || intervals.length == 0) return 0;
Arrays.sort(intervals, (Interval a, Interval b) -> a.start - b.start);
print(intervals);
System.out.println("====================");
// MinHeap
Queue<Interval> pq = new PriorityQueue<>((Interval a, Interval b) -> a.end - b.end);
// Add
pq.offer(intervals[0]);
System.out.println("pq.peek(): " + pq.peek().start + "/" + pq.peek().end);
System.out.println("====================");
for(int i=1; i<intervals.length; i++) {
// pq.offer(intervals[i]);
if(pq.peek().end <= intervals[i].start) { // i=1, 4 <= 7
// Remove
pq.poll();
} else {
pq.offer(intervals[i]);
}
}
return pq.size();
}
public static void print(Interval[] intervals) {
for(int i=0; i<intervals.length; i++) {
System.out.println(intervals[i].start + "/" + intervals[i].end);
}
}
}
답변을 작성해보세요.
0
푸샵맨 코딩스터디
지식공유자2021.03.12
안녕하세요~~
네 소스를 봤는데요 ...잘 못 찾겠습니다.
PrioryQueue 의 사이즈가 -1이 나온다는게 좀 이상하네요
어디서 실행하신건가요??
illhumored
질문자2021.03.12
네 푸샵맨 코딩스터디 님.
먼저, 답변 감사합니다.
질문 올린 문장에.. 의미전달에 오해가 있을 수 있었겠네요.
pq.size() = -1 이 아닌 pq.sizq()-1 의 값이 나오는 현상입니다.
main 함수 안에 주석 처리된, 샘플로 사용했던 input 으로 예를들면
// 2 -> 2, true
// Interval in1 = new Interval(0, 30);
// Interval in2 = new Interval(4, 9);
// Interval in3 = new Interval(5, 15);
// Interval in4 = new Interval(10, 16);
// Interval[] intervals = {in1, in2, in3, in4};
1. 위 케이스는 pq.size() = 2 로 올바르게 처리되지만
// 1 -> 0, False
// Interval in1 = new Interval(7, 10);
// Interval in2 = new Interval(2, 4);
// Interval[] intervals = {in1, in2};
2. 위 케이스는 pq.size() = 1 이 나와야 하지만 0 이 나오며
// 2 -> 1, False
Interval in1 = new Interval(0, 30);
Interval in2 = new Interval(5, 10);
Interval in3 = new Interval(15, 20);
Interval[] intervals = {in1, in2, in3};
3. 위 케이스는 pq.size() = 2 가 나와야 하지만 1 이 나옵니다.
저도 다시 코드에 문제는 없는지 살펴보겠습니다..
답변 1