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("%dn", nsold); return 0; }