Apartment Hunting Problem

Hi, let's encounter a problem from the Algoexpert array section. The problem is -

Problem Statement — You’re looking to move into a new apartment, and you’re given a list of blocks where each block contains some services that it offers. In order to pick your apartment, you want to optimize its location in such a way that the maximum distance to any services that you care for is minimized.

Example —

blocks = [ { “gym” : true, “school” : true, “store” : false } ,{ “gym” : true, “school” : true, “store” : false } ,{ “gym” : true, “school” : true, “store” : false } ,{ “gym” : true, “school” : true, “store” : false } ,{ “gym” : true, “school” : true, “store” : false } ]

requirements = [ “gym”, “school”, “store” ]

Solution Approach — There are multiple possible answers to that question, where we can basically establish a trade-off between space and time complexities.

Suggested approach — Initialize a vector that stores the farthest distance of a particular service for every block with INT_MIN. Now for every block, go through every requirement and find the closest block that satisfies that requirements and change vector value for that block with a minimum of the current value and maximum distance for any requirement. At the end return the index the minimum value in the vector.

I hope it helps :-)