After reading this article, you can try to solve the following problems:

252. Conference Room (Easy)

253. Conference Room II (Medium)

Before the interview, I was asked a very classic and very practical algorithm topic: conference room arrangement.

Buckle the similar problem is a member topic, you may not be able to do, but for this classic algorithm, master the train of thought or necessary.

Please calculate the minimum number of meeting rooms you need to apply for.

The function signature is as follows:

Int minMeetingRooms(int[][] meetings);Copy the code

Meetings = [[0,30],[5,10],[15,20]], the algorithm should return 2, because the last two meetings and the first meeting time conflict, apply for at least two meeting rooms to make all meetings run smoothly.

If there is overlap between meetings, you need to apply for additional meeting rooms. To find the minimum number of meeting rooms, you need to calculate the maximum number of meetings going on at the same time.

In other words, if you think of the start and end times of each meeting as a line interval, then they’re asking you to figure out how many overlapping intervals there are at most, and that’s it.

For this kind of scheduling problem, essentially speaking is interval scheduling problem, nine times out of ten have to sort, and then find the rule to solve.

Topics extend

We’ve written a lot about interval scheduling before, so here’s how to sort it out for you:

In the first scenario, suppose there is only one conference room and there are several meetings. How do you get as many meetings as possible into that conference room?

This problem requires sorting these meetings (intervals) by end time (right endpoint) and processing, as described above for greedy algorithms for time management.

In the second scenario, you are given a number of short video clips, and a long video clip, and you are asked to select as few clips as possible from the short clip and splice together the long one.

This problem requires sorting these video clips (intervals) by start time (left endpoint) and processing, as shown in the previous video clip to cut out a greedy algorithm.

In the third scenario, you are given several intervals, some of which may be short and completely covered by other intervals. Please delete these covered intervals.

The problem requires sorting these intervals by their left endpoints, and then finding and deleting fully covered intervals, as described in deleting covered intervals.

In the fourth scenario, you are given several sections, and you are asked to merge all the sections with overlapping parts.

In this problem, these intervals need to be sorted according to the left endpoints to facilitate the identification of overlapping intervals. See merging overlapping intervals in the previous article.

In the fifth scenario, two departments book several time periods for the same conference room at the same time. Please calculate the conflict time period of the conference room.

The problem is to give you a list of two sets of intervals and ask you to find the intersection of the two sets of intervals. This requires you to sort the intervals by their left endpoints, as described in the previous section on interval intersection problems.

Sixth scenario, suppose there is only one conference room now, and there are several meetings, how to arrange the meeting so that the idle time of the conference room is the least?

This one takes a lot of thinking, and it’s basically a variation of the 0-1 knapsack problem:

Meeting room can be regarded as a backpack, each meeting can be regarded as an item, the value of the item is the length of the meeting, how do you choose the item (meeting) to maximize the value in the backpack (meeting time)?

Of course, the constraint here is not a maximum weight, but that items (meetings) cannot conflict with each other. Sort each meeting according to the end time, and then refer to the 0-1 knapsack problem detailed solution ideas can be solved, and I can write about this problem when I have the opportunity.

The seventh scenario, the one described in this article, gives you a number of meetings that allow you to reasonably apply for a conference room.

Ok, so with so many examples, let’s see how we can solve today’s problem.

Subject analysis

To repeat the essence of the title:

Give you a number of time intervals and let you calculate how many intervals overlap “at most” at the same time.

The point of the question is, given any given moment in time, can you name how many meetings are going on at that moment?

If I can do that, I will go through all The Times and find the maximum number of meeting rooms to apply for.

Is there a data structure or an algorithm that gives me a number of intervals, and I know how many intervals overlap at each location?

Regular readers can certainly relate to an algorithmic trick mentioned earlier: the difference array trick.

Think of the timeline as an array with an initial value of 0, where each time interval [I, j] is a subarray, and each time interval has a meeting, so I increment each element in the subarray by one.

Finally, don’t I know how many meetings there are at any given moment? If I go through the array, don’t I know that I need at least a few conference rooms?

For example, if we say meetings = [[0,30],[5,10],[15,20]], then we add one to each of the [0,30],[5,10],[15,20] index intervals.

Remember, the difference array trick can add or subtract the entire interval at O(1) time, so we can use that to solve this problem.

However, the efficiency of this solution is not high, so I am not prepared to write a specific difference array solution, referring to the principle of difference array skills, interested readers can try to achieve their own.

Based on the idea of difference arrays, we can derive a more efficient and elegant solution.

We first projected the time intervals for these meetings:

The red dots represent the start time of each meeting and the green dots represent the end time of each meeting.

Now imagine a line with a counter that scans the time line from left to right, incrementing the counter count by one for each red dot and decreasing it by one for each green dot:

In this way, how many meetings are going on at any moment is the value of the counter count, and the maximum value of count is the number of meeting rooms to be applied.

Readers familiar with the difference array technique can see at a glance that this scan line is actually the traversal process of the difference array, so we say that this is the solution derived from the difference array technique.

Code implementation

So, how do you write code to implement this scanning process?

First, projecting the intervals is equivalent to sorting the starting and ending points of each interval separately:

int minMeetingRooms(int[][] meetings) { int n = meetings.length; int[] begin = new int[n]; int[] end = new int[n]; For (int I = 0; i < n; i++) { begin[i] = meetings[i][0]; end[i] = meetings[i][1]; } arrays.sort (begin); Arrays.sort(end); / /... }Copy the code

Then it is simple: the line goes from left to right, incrementing the counter when it encounters a red dot, and decrement the counter when it encounters a green dot. The maximum value of count is the answer:

int minMeetingRooms(int[][] meetings) { int n = meetings.length; int[] begin = new int[n]; int[] end = new int[n]; for(int i = 0; i < n; i++) { begin[i] = meetings[i][0]; end[i] = meetings[i][1]; } Arrays.sort(begin); Arrays.sort(end); Int count = 0; Int res = 0, I = 0, j = 0; While (I < n &&j < n) {if (begin[I] < end[j]) { i++; } else {// Scan a green dot count--; j++; } // Record the maximum value in the scan process res = math.max (res, count); } return res; }Copy the code

The two-pointer technique is used here, so you can think of pointer I as the scan line, and you can simulate the progress of the scan line based on the relative positions of I and J.

So we’re done with this problem. Of course, this problem can also be deformed, for example, give you a number of meetings, ask you k conference room is enough, in fact, you use the solution code of this article, can also be easily solved.

Read next:

Interval problem series collection

View more quality algorithm articles click here, hand with your brush force buckle, committed to the algorithm to speak clearly! My algorithm tutorial has received 90K star, welcome to like!