In the process of preparing for programming interviews, it is very important to solve specific algorithm problems. Today, we will solve the problem of ‘Allocating Meeting Rooms’ in Java. This problem helps in understanding algorithms and data structures, and focuses on finding the optimal solution that satisfies specific conditions.
Problem Description
Various meetings occur within specific time intervals. Each meeting has a start time and an end time. The goal is to allocate all meetings in the minimum number of meeting rooms possible.
Problem Definition
Title: Allocate Meeting Rooms Input: - Given several meetings, each defined by a start time and an end time (start, end). - Meetings are given in the form [[start1, end1], [start2, end2], ...]. Output: - Return the number of meeting rooms required when allocating rooms to minimize the number of meeting rooms.
Example Input and Output
Input: [[0, 30], [5, 10], [15, 20]] Output: 2 (2 meeting rooms needed) Input: [[7, 10], [2, 4]] Output: 1 (1 meeting room needed)
Solution Approach
To solve this problem, we can sort the meetings based on their start times and use a priority queue to manage the end times of currently used rooms. Then, we sequentially check each meeting to decide whether to add a new room or not.
Algorithm Steps
- Sort the meetings in ascending order based on their start times.
- Use a priority queue to manage the end times of meeting rooms.
- While checking each meeting, add the meeting to the room that ends the earliest or allocate a new room.
- Finally, return the number of rooms used.
Java Code Implementation
Below is the Java code implemented based on the above approach:
import java.util.Arrays;
import java.util.PriorityQueue;
public class MeetingRooms {
public int minMeetingRooms(int[][] intervals) {
if (intervals.length == 0) {
return 0;
}
// Sort the meetings based on their start times.
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
// Use a priority queue to manage the end times of meeting rooms.
PriorityQueue minHeap = new PriorityQueue<>();
for (int[] interval : intervals) {
// Compare the start time of the current meeting with the end time of the earliest meeting room
if (!minHeap.isEmpty() && interval[0] >= minHeap.peek()) {
minHeap.poll(); // Free up the room
}
// If a new room is needed, add the end time
minHeap.add(interval[1]);
}
// Return the number of meeting rooms used
return minHeap.size();
}
public static void main(String[] args) {
MeetingRooms meetingRooms = new MeetingRooms();
int[][] intervals = {{0, 30}, {5, 10}, {15, 20}};
System.out.println("Number of meeting rooms needed: " + meetingRooms.minMeetingRooms(intervals));
int[][] intervals2 = {{7, 10}, {2, 4}};
System.out.println("Number of meeting rooms needed: " + meetingRooms.minMeetingRooms(intervals2));
}
}
Results and Time Complexity
Running the above code accurately calculates the number of meeting rooms required for the given meetings. The time complexity of this algorithm is as follows:
- Sorting the meetings takes
O(n log n). - Checking each meeting while adding or removing from the priority queue takes
O(n log k).
As a result, the overall time complexity can be analyzed as O(n log n + n log k), where n is the number of meetings and k is the number of meeting rooms in use.
Conclusion
In this article, we examined the approach to solving the ‘Allocating Meeting Rooms’ problem and the implementation of Java code in detail. We hope it has been helpful in preparing for coding tests, and that you can further enhance your problem-solving skills through data structures and algorithms.