CSES - Room Allocation

Explanation

In this problem, we're asked the minimum number of rooms needed to accommodate $n$ customers, who arrive and leave on set days. Let's sort each customer by their start time so that we do not have a customer arriving at say, time 3, occupying a room before a customer that arrives at time 2.

Now, we can iterate through the customers while maintaining a minimum priority queue that stores the departure times of customers we've already processed. For each customer, we check to see if the minimum element in the priority queue is less than the arrival time of the new customer.

• If this is true, that means a room previously occupied has opened up, so we remove the minimum element from the priority queue and replace it with the new customer's departure time. The new customer will be allocated to the same room as the customer who departed.
• Otherwise, all the rooms are full, so we need to allocate another room for the customer and add it to the priority queue.

We can determine $k$ by finding the maximum size the priority queue reaches as we iterate through the customers.

Implementation

Time Complexity: $\mathcal{O}(n\log n)$

Copy
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;

const int MAX_N = 2e5;

int N;
int ans[MAX_N];
vector<pair<pair<int, int>, int>> v(MAX_N);

Copy
import java.io.*;
import java.util.*;

public class RoomAllocation {
	public static void main(String[] args) {
		FastIO io = new FastIO();

		int n = io.nextInt();
		Customer[] customers = new Customer[n];
		for (int i = 0; i < n; i++) {