/ Array

Meeting Rooms Leetcode

Problem Statement

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.
For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.


Solution Explanation

The meeting rooms problem or the airplanes on the runway problem are all similar and they basically wants you to find out the min number of the scarce recources you need given the demand.

In the above example, you can see there are mutiple people who booked a meeting room and mentioned the start and end time of their meetings. To meet this demand, the operations team would need to know how many meeting rooms they need to facilitate to the team. In the case of airlines problem, you will be usually given a list of departure and arrival times and be asked to find out the minimum number of runways you require to enable smooth flow of air traffic.

We sort the intervals based on the start time first, have a counter, compare each start time and the corresponding end time by adding end times to a priority queue. If start time is lesser, increment the counter, else pop the end time from queue.

Here's the java implementation for meeting rooms,

public class MeetingRooms2 {

	public static void main(String[] args) {
		Interval[] intervals = new Interval[3];
		intervals[0] = new Interval(0, 30);
		intervals[1] = new Interval(5, 10);
		intervals[2] = new Interval(15, 20);
		System.out.println("Min no of meeting rooms required is " + findMinNoOfMeetingRooms(intervals));

	}

	public static int findMinNoOfMeetingRooms(Interval[] intervals) {
		if (intervals == null || intervals.length == 0)
			return 0;
		Arrays.sort(intervals, new Comparator<Interval>() {
			public int compare(Interval i1, Interval i2) {
				return i1.start - i2.start;
			}
		});
		PriorityQueue<Integer> queue = new PriorityQueue<>();
		int count = 1;
		queue.offer(intervals[0].end);
		for (int i = 1; i < intervals.length; i++) {
			if (intervals[i].start < queue.peek()) {
				count++;
			} else {
				queue.poll();
			}
			queue.offer(intervals[i].end);
		}

		return count;
	}

	static class Interval {
		int start;
		int end;

		public Interval(int start, int end) {
			this.start = start;
			this.end = end;
		}
	}

}
Time Complexity

Since we sort the input first and the compare times, the total time complexity is O(nlogn) and space complexity is O(n), where n is the number of intervals.