In this 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, xj, and a minimum price, yj. You also have n clients, and each client i want a house with an area greater than ai and a price less than or equal to pi.
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?
Problem solution in Python.
#!/bin/python3
import os
import sys
#
# Complete the realEstateBroker function below.
#
def realEstateBroker(clients, houses):
#
# Write your code here.
#
n = len(clients)
m = len(houses)
houses.sort()
res = 0
bought_clients = [False] * n
for house in houses:
x, y = house
eligible_clients = [(clients[i][1], i) for i in range(n) if (not bought_clients[i]) and clients[i][0] < x and clients[i][1] >= y]
if len(eligible_clients):
p, j = min(eligible_clients)
bought_clients[j] = True
res += 1
return res
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
nm = input().split()
n = int(nm[0])
m = int(nm[1])
clients = []
for _ in range(n):
clients.append(list(map(int, input().rstrip().split())))
houses = []
for _ in range(m):
houses.append(list(map(int, input().rstrip().split())))
result = realEstateBroker(clients, houses)
fptr.write(str(result) + '\n')
fptr.close()
Problem solution in Java.
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();
}
}
Problem solution in C++.
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
struct house;
struct client {
int a;
int p;
};
struct house {
int x;
int y;
};
//somewhat like an adjacency matrix
bool** chg;
//visited houses (reset at each client)
bool* visited;
//the client matched for each house
//necessary for rematching previous clients
int* hmatch;
int hcount;
//try to match client ci to an unpurchased house
//standard bipartite matching algorithm
bool match(int ci )
{
//try all houses
for (int i = 0; i < hcount; i++)
{
//see if house meets client's preferences
if(chg[ci][i] == true)
{
//make sure we don't loop
if(visited[i] == false)
{
visited[i] = true;
//house hasn't been matched yet
if (hmatch[i] == -1)
{
hmatch[i] = ci;
return true;
} else if (match(hmatch[i])) {
//house was previously matched; try to rematch the client
hmatch[i] = ci;
return true;
}
}
}
}
return false;
}
int main() {
int n, m;
cin >> n >> m;
hcount = m;
client* cl = new client[n];
house* hl = new house[m];
chg = new bool*[n];
hmatch = new int[m];
for (int i = 0; i < n; i++)
{
chg[i] = new bool[m];
cin >> cl[i].a >> cl[i].p;
}
for (int i = 0; i < m; i++)
{
hmatch[i] = -1;
cin >> hl[i].x >> hl[i].y;
}
for( int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
if(cl[i].a < hl[j].x && cl[i].p >= hl[j].y)
{
chg[i][j] = true;
} else {
chg[i][j] = false;
}
}
}
int count = 0;
//try to match each client
for(int i = 0; i < n; i++)
{
//reset the visited houses list once per client
visited = new bool[m];
for (int j = 0; j < m; j++)
{
visited[j] = false;
}
//try to match the client; count matches
if (match(i))
{
count++;
}
}
cout << count << endl;
return 0;
}
Problem solution in C.
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
struct AP {
int a; // area
int p; // price
};
static int nclients;
static int nhouses;
static struct AP client[1000];
static struct AP house[1000];
static int hashouse[1000];
static int nsold = 0;
static int read_int(void)
{
int r, n;
r = scanf("%d", &n);
assert(r == 1);
return n;
}
static 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;
}
static 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(void)
{
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;
}
0 Comments