# Real Estate Broker

# Real Estate Broker

+ 0 comments I just want to say that O(n^2) in editorial for this problem seems a wrong time complexity. That is because the total number of edges is O(mn). If one applies a standard Ford-Fulkerson algorithm, it is O(|E|f_max) = O(mn^2) in the problem setting. If one aims better one, try Horpcroft-Karp's algorithm for the bipartite matching. It should give you O(sqrt(|V|)|E|) = O(mn(m+n)^0.5) time complexity.

+ 1 comment This problem can be solved by greedy in O(nlogn), which can be easily implemented.

#include <bits/stdc++.h> using namespace std; typedef long long LL; #define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i) #define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i) #ifdef zerol #define dbg(args...) do { cout << "\033[32;1m" << #args<< " -> "; err(args); } while (0) #else #define dbg(...) #endif void err() { cout << "\033[39;0m" << endl; } template<typename T, typename... Args> void err(T a, Args... args) { cout << a << ' '; err(args...); } // ----------------------------------------------------------------------------- const int maxn = 1E3 + 100; struct P { int s, p, tp; }; vector<P> a; int n, m; set<int> S; int main() { int x, y; cin >> n >> m; FOR (_, 0, n) { scanf("%d%d", &x, &y); a.push_back({x, y, 1}); } FOR (_, 0, m) { scanf("%d%d", &x, &y); a.push_back({x, y, 0}); } sort(a.begin(), a.end(), [](const P& a, const P& b)->bool { return a.p < b.p || (a.p == b.p && a.tp < b.tp); }); int ans = 0; for (P& u: a) { if (u.tp == 0) S.insert(u.s); else { auto it = S.upper_bound(u.s); if (it != S.end()) { ++ans; S.erase(it); } } } cout << ans << endl; }

+ 0 comments Can anyone help me figure out what is wrong with this ? so basically i saw the bidders for a house, and gave it to the guy who can afford less number of houses, but it doesnt always work

+ 2 comments There is a greedy solution as follow:

- Sort the houses based on area.
- Sell house to client who is eligible and who buy at minimum price.
- Note only sell house once to a particualar client.

Link solution: https://ideone.com/OO9sJL

+ 0 comments The whole Real Estate thing got way too complicated in the last few years. I needed to sell my property as I were planning on relocation and it turned into a nightmare until I contacted a company that just simply said we buy houses with no hassle for you and that was right what a needed to hear.

Sort 26 Discussions, By:

Please Login in order to post a comment