미해결
정말 쉽게 풀어보는 코딩 테스트 top 기본 문제 (with 자바)
MeetingRoom2 질문드립니다.
안녕하세요. 강사님.
미팅룸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);
}
}
}