Hackerrank Real Estate Broker Solution

#include <iostream>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <cstdlib>
#include <functional>
#include <utility>
typedef unsigned long long ull;
using namespace std;
vector<vector<int> > cl,ho;
vector<int> match(1001);
bool buy(int u,bitset<1001> &seen){
    int a=cl[u][0],p=cl[u][1];
    vector<vector<int> >::iterator it=upper_bound(ho.begin(),ho.end(),cl[u],[](const vector<int> &l,const vector<int> &r){
        if(l[0]<r[0])
            return true;
        if(l[0]==r[0]&&l[1]<r[1])
            return true;
        return false;
    });
    while(it!=ho.end()){
        if((*it)[1]<=p&&!seen[it-ho.begin()]){
            seen[it-ho.begin()]=1;
            if(!match[it-ho.begin()]||buy(match[it-ho.begin()],seen)){
                match[it-ho.begin()]=u;
                return true;
            }
        }
        it++;
    }
    return false;
}
int main(){
    int n,h;
    cin>>n>>h;
    cl.push_back({0,0});
    ho.push_back({0,0});
    for(int i=0;i<n;i++){
        int a,p;
        cin>>a>>p;
        cl.push_back({a,p});
    }
    for(int i=0;i<h;i++){
        int a,p;
        cin>>a>>p;
        ho.push_back({a,p});
    }
    sort(cl.begin(),cl.end(),[](auto &l,auto &r){
        if(l[0]<r[0])
            return true;
        if(l[0]==r[0]&&l[1]<r[1])
            return true;
        return false;
    });
    sort(ho.begin(),ho.end(),[](auto &l,auto &r){
        if(l[0]<r[0])
            return true;
        if(l[0]==r[0]&&l[1]<r[1])
            return true;
        return false;
    });
    int ans=0;
    for(int i=1;i<=n;i++){
        bitset<1001> seen;
        if(buy(i,seen))
            ans++;
        // cout<<ans<<endl;
    }
    cout<<ans<<endl;
    return 0;
}

Comments