Problem Link - Maximum Apartment Buyers in Chefland
Problem Statement:
In Chefland, there are n people, each of whom wants to buy one apartment from a set of m available apartments. Each person has a certain budget and will only buy an apartment if its price is less than or equal to their budget. The task is to determine the maximum number of people who can buy an apartment based on the given budget array (size n) and price array (size m).
Approach:
The key idea of this problem is to match as many people with apartments as possible. To achieve this, we can follow a greedy approach, where we attempt to assign the cheapest available apartment to each person whose budget can accommodate it.
-
Sorting: Sort both the budget and price arrays in ascending order to efficiently match each person with the cheapest available apartment.
-
Matching Process:
-
Use two pointers: one for the budget array (i) and one for the price array (j).
-
Traverse both arrays:
- If budget[i] is greater than or equal to price[j], the person can afford the apartment. Increment the count and move to the next apartment (j++).
- If the person cannot afford the apartment, move to the next person (i++).
-
Repeat until all people are considered or all apartments are matched.
-
-
Result: The final count indicates the maximum number of people who can buy apartments.
Time Complexity:
-
Sorting: Takes O(n log n) for the budget array and O(m log m) for the price array.
-
Matching Process: The matching loop runs in O(n + m) time.
-
Overall Time Complexity: O(n log n + m log m).
Space Complexity:
The space complexity is O(1), as we only use a few extra variables (i, j, count) for tracking indices and counts.