[[0,30],[5,10],[15,20]], answer should be [[0, 0], [1, 1], [2, 1]]. Explanation: Meeting [0, 30] happens in Room-0, Meeting [5,10] happens in Room-1. Room-1 gets freed at t = 10, so it is then used for Meeting [15, 20]Update:
Test Cases
input: [[0, 30], [5, 10], [15, 20]]
output: 2 rooms [meeting index, room number]-> [[0, 0], [1, 1], [2, 1]]
explained in the problem descriptioninput: [[4, 8], [5, 10], [6, 8], [9, 16], [15, 20]]
output: 3 rooms -> [[0, 0], [1, 1], [2, 2], [3, 0], [4, 1]]
* Meeting 0 runs from 4 to 8 in room 0
* Meeting 1 runs from 5 to 10 in room 1.
* Meeting 0 is still running so room 0 isn't available, so take a new room, room 1.
* Meeting 2 runs from 6 to 8 in room 2.
* Meeting 0 and 1 are still running so rooms 0 and 1 aren't available, so take a new room, room 2.
* Meeting 3 runs from 9 to16 in room 0.
* Meeting 0 and 2 are over, choose room 0 since its numerically lower
* Meeting 4 runs from 15 to 20.
* Meeting 0, 1 and 2 are over. Room 0 is occupied by meeting 3, so choose room 1input: [4, 6], [6, 8], [9, 16], [15, 20], [5, 10]
output: 2 rooms -> [[0, 0], [1, 0], [2, 0], [3, 1], [4, 1]]Solution (a slight modification of @ikna's solution)
public void testMeetings() {
getMinimumMeetings(new int[][]{{0, 30, 0}, {5, 10, 1}, {15, 20, 2}});
}
public void getMinimumMeetings(int[][] meetings) {
var meetingsByRoom = minMeetings(meetings);
System.out.println(meetingsByRoom);
System.out.println(Collections.max(meetingsByRoom.values()) + 1); // max rooms required
}
private Map<Integer, Integer> minMeetings(int[][] meetings) {
Arrays.sort(meeting, Comparator.comparingInt(i -> i[0]));
var minHeap = new PriorityQueue<int[]>(Comparator.comparingInt(i -> i[0]));
var meetingsByRoom = new TreeMap<Integer, Integer>();
var meetingHeap = IntStream.range(0, meetings.length)
.boxed()
.collect(Collectors.toCollection(PriorityQueue::new));
for (var meeting : meetings) {
var start = job[0];
var end = job[1];
while (!minHeap.isEmpty() && start >= minHeap.peek()[0])
meetingHeap.add(minHeap.poll()[1]);
if (!meetingHeap.isEmpty()) {
var nextMeetingId = meetingHeap.poll();
minHeap.add(new int[]{end, nextMeetingId});
meetingsByRoom.put(job[2], nextMeetingId);
}
}
return meetingsByRoom;
}