Help with CSES problem Room Allocation

general
,
1

Here is the link to the problem CSES - Room Allocation. 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.)

3 Likes
2
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();
}
8 Likes
3

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

4

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

5

**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;

}

1 Like
6

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

7

thanks but it would be more helpful if you explain the logic

8

Look …using two pointers we are iterating such that we add a customer when ever someone’s arriving dates crosses your current departure date .
Why ? its simple because at that moment only you can free your very first room and each time you do so you map that free room with the one that arrived recently.