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?
time complexity is O(NlogN + MlogM + N*M)
space complexity is O(1)
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 🙂
#!/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) sold = 0 for house in houses: for client in clients: if house >= client and house <= client: 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) m = int(nm) 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.