HackerRank ‘Real Estate Broker’ Solution

Short Problem Definition:

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 wants a house with an area greater than ai and a price less than or equal to bi.

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?

Link

Real Estate Broker

Complexity:

time complexity is O(NlogN + MlogM + N*M)

space complexity is O(1)

Execution:

This challenge sounds pretty complex, but this greedy solution works perfectly. Sort houses by size, start selling the smallest houses first. Bigger houses can always be sold since there is a bigger pool of buyers for them. Sell each house to the buyer that has the smallest pool of money available.

Don’t overcomplicate the problem with graph algorithms 🙂

Solution:
#!/bin/python

from __future__ import print_function

import os
import sys

#
# Complete the realEstateBroker function below.
#
def realEstateBroker(clients, houses):
    houses = sorted(houses)
    clients = sorted(clients, key = lambda x: x[1])
    
    sold = 0
    
    for house in houses:
        for client in clients:
            if house[0] >= client[0] and house[1] <= client[1]:
                sold += 1
                clients.remove(client)
                break
    
    return sold

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    nm = raw_input().split()

    n = int(nm[0])

    m = int(nm[1])

    clients = []

    for _ in xrange(n):
        clients.append(map(int, raw_input().rstrip().split()))

    houses = []

    for _ in xrange(m):
        houses.append(map(int, raw_input().rstrip().split()))

    result = realEstateBroker(clients, houses)

    fptr.write(str(result) + '\n')

    fptr.close()


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwitterredditpinterestlinkedin