HackerRank Real Estate Broker Problem Solution
In this post, we will solve HackerRank Real Estate Broker Problem Solution.
You are a real estate broker in ancient Knossos. You have m unsold houses, and each house j has an area, i, and a minimum price, yi. You also have n clients, and each client wants a house with an area greater than ai and a price less than or equal to p;.
Each client can buy at most one house, and each house can have at most one owner. What is the maximum number of houses you can sell?
Input Format
The first line contains two space-separated integers describing the respective values of n (the number of clients) and m (the number of houses).
Each line i of the n subsequent lines contains two space-separated integers describing the respective values of ai and pi for client i.
Each line j of the m subsequent lines contains two space-separated integers describing the respective values of xi and yi for house j.
Output Format
Print a single integer denoting the maximum number of houses you can sell.
Sample Input 0
3 3
5 110
9 500
20 400
10 100
2 200
30 300
Sample Output 0
2
Real Estate Broker C Solution
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
struct AP {
int a; // area
int p; // price
};
int nclients;
int nhouses;
struct AP client[1000];
struct AP house[1000];
int hashouse[1000];
int nsold = 0;
int read_int()
{
int r, n;
r = scanf("%d", &n);
assert(r == 1);
return n;
}
int compareArea(const void *a, const void *b)
{
const struct AP *x = a;
const struct AP *y = b;
if (x->a != y->a)
return x->a - y->a;
return x->p - y->p;
}
int comparePrice(const void *a, const void *b)
{
const struct AP *x = a;
const struct AP *y = b;
if (x->p != y->p)
return x->p - y->p;
return x->a - y->a;
}
int main()
{
int i, j;
nclients = read_int();
nhouses = read_int();
for (i = 0; i < nclients; i++) {
client[i].a = read_int();
client[i].p = read_int();
}
for (i = 0; i < nhouses; i++) {
house[i].a = read_int();
house[i].p = read_int();
}
qsort(house, nhouses, sizeof house[0], compareArea);
qsort(client, nclients, sizeof client[0], comparePrice);
for (i = 0; i < nhouses; i++) {
for (j = 0; j < nclients; j++)
if (!hashouse[j] && house[i].a >= client[j].a && house[i].p <= client[j].p) {
hashouse[j] = 1;
nsold += 1;
break;
}
}
printf("%d\n", nsold);
return 0;
}
Real Estate Broker C++ Solution
#include<bits/stdc++.h>
#define in freopen("input.txt","r",stdin)
#define out freopen("output.txt","w",stdout)
#define inp freopen(".in","r",stdin)
#define outp freopen(".out","w",stdout)
using namespace std;
#define pb push_back
#define pf push_front
#define p_f pop_front
#define p_b pop_back
#define LL long long int
#define LD long double
#define MP make_pair
#define sqr(x) (x*x)
#define nwl pr("\n")
#define fi first
#define dist(x,y,xx,yy) sqrt( (x-xx)*(x-xx)+(y-yy)*(y-yy) )
#define lenint int intsi(int x){ int cnt=0; while(x>0){cnt++;x/=10;} return (cnt); }
#define se second
#define all(v) v.begin(),v.end()
#define sc scanf
#define DEBUG(a) cout<<#a<<" -> "<<a<<endl;
#define pr printf
#define si size()
#define str strlen
#define time clock()/(double)CLOCKS_PER_SEC
#define gcd LL GCD(LL a,LL b){ if(b==0)return a;else return GCD(b,a%b); }
const int INF=(-1u)/2;
const long long int INF2=(-1ull)/2;
int a,b,c[100010],us[100010],i,j,k,n,m,timer=0,x,y;
int cnt=0,fl=0,a2,a3=-1000000,ans=0,l,r;
pair<int,int>p[100010],pp[100010];
int main()
{
// in;
// ios_base::sync_with_stdio(0);
cin>>n>>m;
for( i=0;i<n;i++ )
{
cin>>x>>y;
p[i]=MP(x*-1,y);
}
for( i=0;i<m;i++ )
{
cin>>x>>y;
pp[i]=MP(x,y*-1);
}
sort(pp,pp+m);
sort(p,p+n);
for( i=0;i<m;i++ )pp[i].se*=-1;
for( i=0;i<n;i++ )p[i].fi*=-1;
for( i=0;i<n;i++ )
{
fl=-1;
for( j=0;j<m;j++ )
{
if( us[j] )continue;
if( pp[j].fi>p[i].fi && pp[j].se<=p[i].se )
{
if( fl==-1 )fl=j;
if( pp[j].se>pp[fl].se )fl=j;
}
}
if(fl!=-1)
{
us[fl]=1;
ans++;
}
}
cout<<ans<<endl;
return 0;
}
Real Estate Broker C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
static int INFINITE = Int32.MaxValue;
static int NILL = 0;
public struct Client
{
public int idx, area, prize, nill_id;
public Client(int p_idx, int p_area, int p_prize)
{
idx = p_idx;
area = p_area;
prize = p_prize;
nill_id = 0;
}
}
public struct House
{
public int idx, area, prize, nill_id;
public House(int p_idx, int p_area, int p_prize)
{
idx = p_idx;
area = p_area;
prize = p_prize;
nill_id = 0;
}
}
static int max(int n, int m) {
if(n>m) return n;
else return m;
}
static List<int>[] buildGraph(int n, int m,IEnumerable<Client> clients, IEnumerable<House> houses) {
List<int>[] graph = new List<int>[n+1];
IEnumerable<int> relatedHouses;
for(int i=0; i<=n; i++) {
graph[i] = new List<int>();
}
var query = from client in clients
join house in houses
on client.nill_id equals house.nill_id
where client.area <= house.area
&& client.prize >= house.prize
select new { cIndex = client.idx, hIndex = house.idx };
var agroupedData = query.GroupBy(x => x.cIndex)
.Select(y => new {cIndex = y.Key,
rHouses = y.ToList()}
);
foreach(var x in agroupedData) {
graph[x.cIndex].AddRange(x.rHouses.Select(y => y.hIndex));
}
return graph;
}
static bool bfs(List<int>[] graph, int[] pairU, int[] pairV, int[] dist) {
Queue<int> queue = new Queue<int>();
int u;
for(int i=1; i<pairU.Length; i++) {
// free vertex are marked
if(pairU[i]==NILL) {
dist[i]=0;
queue.Enqueue(i);
}
else dist[i]=INFINITE;
}
dist[NILL] = INFINITE;
while(queue.Any()) {
u = queue.Dequeue();
if(dist[u] < dist[NILL]) {
foreach(int v in graph[u]) {
// edge not yet considered
if(dist[pairV[v]] == INFINITE) {
dist[pairV[v]] = dist[u] + 1;
queue.Enqueue(pairV[v]);
}
}
}
}
// an augmenting path has been founded
return dist[NILL] != INFINITE;
}
static bool dfs(int u, List<int>[] graph, int[] pairU, int[] pairV, int[] dist) {
if(u != NILL) {
foreach(int v in graph[u]) {
if(dist[pairV[v]] == dist[u]+1) {
if(dfs(pairV[v], graph, pairU, pairV, dist)) {
pairV[v] = u;
pairU[u] = v;
return true;
}
}
}
dist[u]=INFINITE;
return false;
}
return true;
}
static int realEstateBroker(int n, int m, List<Client> clients, List<House> houses) {
int[] pairU = new int[n+1];
int[] pairV = new int[m+1];
int[] dist = new int[n+1];
for (int u=0; u<n; u++)
pairU[u] = NILL;
for (int v=0; v<m; v++)
pairV[v] = NILL;
int result = 0;
List<int>[] graph = buildGraph(n, m,clients, houses);
while(bfs(graph, pairU, pairV, dist)) {
for(int u=1; u<=n; u++) {
if(pairU[u]==NILL && dfs(u, graph, pairU, pairV, dist)) {
result++;
}
}
}
return result;
}
static void Main(string[] args) {
TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);
string[] nm = Console.ReadLine().Split(' ');
int n = Convert.ToInt32(nm[0]);
int m = Convert.ToInt32(nm[1]);
List<Client> clients = new List<Client>();
int idx;
int[] clientData;
for (int clientsRowItr = 0; clientsRowItr < n; clientsRowItr++) {
idx=clientsRowItr;
clientData = Array.ConvertAll(Console.ReadLine().Split(' '), clientsTemp => Convert.ToInt32(clientsTemp));
clients.Add(new Client(++idx, clientData[0], clientData[1]));
}
List<House> houses = new List<House>();
int[] houseData;
for (int housesRowItr = 0; housesRowItr < m; housesRowItr++) {
idx=housesRowItr;
houseData = Array.ConvertAll(Console.ReadLine().Split(' '), housesTemp => Convert.ToInt32(housesTemp));
houses.Add(new House(++idx, houseData[0], houseData[1]));
}
int result = realEstateBroker(n, m, clients, houses);
textWriter.WriteLine(result);
textWriter.Flush();
textWriter.Close();
}
}
Real Estate Broker Java Solution
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;
public class Solution {
static class Client implements Comparable<Client> {
int minX, maxY;
public Client(int minX, int maxY) {
this.minX = minX;
this.maxY = maxY;
}
@Override
public int compareTo(Client o) {
return (o.minX == this.minX) ? this.maxY - o.maxY : this.minX - o.minX;
}
}
static class House implements Comparable<House> {
int x, y;
public House(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public int compareTo(House o) {
return (o.x == this.x) ? this.y - o.y : this.x - o.x;
}
}
static int realEstateBroker(int[][] clients0, int[][] houses0) {
int cc = clients0.length;
int hc = houses0.length;
List<Client> cs = new ArrayList<>(cc+1);
List<House> hs = new ArrayList<>(hc+1);
for (int a[] : clients0) cs.add(new Client(a[0], a[1]));
for (int a[] : houses0) hs.add(new House(a[0], a[1]));
Collections.sort(cs);
Collections.sort(hs);
cs.add(new Client(Integer.MAX_VALUE, Integer.MAX_VALUE));
int c = 0;
int h = 0;
int sold = 0;
TreeSet<Long> ts = new TreeSet<>(); // unique min price
while (c < cc && h < hc) {
while (h < hc && hs.get(h).x <= cs.get(c).minX)
h++;
if (h >= hc)
break;
while (c < cc && hs.get(h).x > cs.get(c).minX) {
ts.add(cs.get(c).maxY * 1000L + c);
c++;
}
while (h < hc && hs.get(h).x <= cs.get(c).minX) {
Long g = ts.ceiling(hs.get(h).y * 1000L);
if (g != null) {
ts.remove(g);
sold++;
}
h++;
}
}
return sold;
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
String[] nm = scanner.nextLine().split(" ");
int n = Integer.parseInt(nm[0].trim());
int m = Integer.parseInt(nm[1].trim());
int[][] clients = new int[n][2];
for (int clientsRowItr = 0; clientsRowItr < n; clientsRowItr++) {
String[] clientsRowItems = scanner.nextLine().split(" ");
for (int clientsColumnItr = 0; clientsColumnItr < 2; clientsColumnItr++) {
int clientsItem = Integer.parseInt(clientsRowItems[clientsColumnItr].trim());
clients[clientsRowItr][clientsColumnItr] = clientsItem;
}
}
int[][] houses = new int[m][2];
for (int housesRowItr = 0; housesRowItr < m; housesRowItr++) {
String[] housesRowItems = scanner.nextLine().split(" ");
for (int housesColumnItr = 0; housesColumnItr < 2; housesColumnItr++) {
int housesItem = Integer.parseInt(housesRowItems[housesColumnItr].trim());
houses[housesRowItr][housesColumnItr] = housesItem;
}
}
int result = realEstateBroker(clients, houses);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedWriter.close();
}
}
Real Estate Broker JavaScript Solution
'use strict';
const fs = require('fs');
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});
process.stdin.on('end', _ => {
inputString = inputString.trim().split('\n').map(str => str.trim());
main();
});
function readLine() {
return inputString[currentLine++];
}
/*
* Complete the realEstateBroker function below.
*/
function realEstateBroker(clients, houses) {
houses.sort((a, b) => a[0] - b[0]);
clients.sort((a, b) => a[1] - b[1]);
let count = 0;
for (let ci = 0; ci < clients.length && houses.length; ci++) {
const [area, price] = clients[ci];
let l = 0;
let r = houses.length;
while (l < r) {
const m = l + ((r - l) >>> 1);
const houseArea = houses[m][0];
// console.log({text: 'bef', area, price, l, r, m, houseArea})
if (houseArea <= area) {
l = m + 1;
} else {
r = m;
}
// console.log({text: 'aft', area, price, l, r, m, houseArea})
}
// console.log({area, price, l, houses});
for (let i = l; i < houses.length; i++) {
const housePrice = houses[i][1];
if (housePrice <= price) {
count++;
houses.splice(i, 1);
break;
}
}
}
// console.log({visited})
return count;
}
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const nm = readLine().split(' ');
const n = parseInt(nm[0], 10);
const m = parseInt(nm[1], 10);
let clients = Array(n);
for (let clientsRowItr = 0; clientsRowItr < n; clientsRowItr++) {
clients[clientsRowItr] = readLine().split(' ').map(clientsTemp => parseInt(clientsTemp, 10));
}
let houses = Array(m);
for (let housesRowItr = 0; housesRowItr < m; housesRowItr++) {
houses[housesRowItr] = readLine().split(' ').map(housesTemp => parseInt(housesTemp, 10));
}
let result = realEstateBroker(clients, houses);
ws.write(result + "\n");
ws.end();
}
Real Estate Broker Python Solution
n, m = map(int, input().split())
buy, house = [], []
for i in range(n):
buy.append(tuple(map(int, input().split())))
for i in range(m):
house.append(tuple(map(int, input().split())))
buy.sort(key=lambda x: x[1])
house.sort()
sold = [False for i in range(n)]
a = 0
for h in range(m):
for c in range(n):
if not sold[c]:
if buy[c][0] <= house[h][0] and buy[c][1] >= house[h][1]:
sold[c] = True
a += 1
break
print(a)