Help with CSES problem Room Allocation

Here is the link to the problem https://cses.fi/problemset/task/1164. Can anyone please help me with this? It would be great if you could give an idea or an approach to solve this question and other questions similar to this along with the code/pseudocode. (Code is completely optional.)

2 Likes
Hint 1

Notice that the numbers themselves are of no relevance, just the order.

Hint 2

Sort something.

Hint 3

Sort the incoming times and outgoing times.

Hint 4

Use two pointers, and the difference between the indexes is the number of people.

Code
#include <iostream>
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
using ll = long long int;
void solve(){
    int n;
    cin>>n;
    vector<pair<int,int>> in(n), out(n);
    set<int> free;
    for(int i=0;i<n;i++){
        cin>>in[i].first>>out[i].first;
        in[i].second = out[i].second = i;
        free.insert(i);
    }
    sort(in.begin(), in.end());
    sort(out.begin(), out.end());
    vector<int> ans(n);
    for(int i=0,j=0;i<n;i++){
        while(j<n && out[j].first<in[i].first){
            free.insert(ans[out[j].second]);
            ++j;
        }
        ans[in[i].second] = *free.begin();
        free.erase(free.begin());
    }
    int k = *max_element(ans.begin(), ans.end()) + 1;
    cout<<k<<"\n";
    for(int i=0;i<n;i++){
        cout<<ans[i] + 1<<" ";
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}
3 Likes

@everule1 Can you please explain the logic a little bit more?

Can anybody please explain why does the above approach work? Please help. :confused: :thinking:

**I have got this code form somewhere, can someone explain its basic logic ?
**

#include <bits/stdc++.h>
#define pb push_back
#define endl ā€˜\nā€™
#define lli long long int
#define li long int
#define ld long double
#define vii vector<int, int>
#define pii pair<int, int>
using namespace std;
const lli mod = 1e9 + 7;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, x, y;
cin >> n;
vector<pair<int, pii>> v;
for (int i = 1; i <= n; i++)
{
cin >> x >> y;
v.pb({x, {-1, i}}); // comes in
v.pb({y, {1, i}}); // goes out
}
sort(v.begin(), v.end());

vector<int> rooms;
int occupied = 0, max_rooms = 0, in_or_out, ind;
int ans[200005];
for (auto ele : v)
{
	in_or_out = ele.second.first;
	ind = ele.second.second;

	if (in_or_out == 1)
	{
		// going out, so add that room number to rooms
		rooms.pb(ans[ind]);
	}
	else if (occupied == rooms.size())
	{
		// no more vacant rooms, so increase number of rooms
		ans[ind] = ++max_rooms;
	}
	else
	{
		// give a room and increase occupancy count
		ans[ind] = rooms[occupied++];
	}
}
cout << max_rooms << endl;
for (int i = 1; i <= n; i++)
{
	cout << ans[i] << " ";
}
return 0;

}

Can someone explain me this code I am a having hard time with it !