Practice/Google/Problem About Interns and Flats Using a Greedy Approach

Problem About Interns and Flats Using a Greedy Approach

CodingMust

Problem

You are managing a summer internship program and need to assign interns to available apartments. Each intern has a preferred location (represented as a position on a number line), and each apartment also has a location on the same number line.

Your goal is to assign each intern to exactly one apartment such that:

• Every intern gets an apartment
• No two interns share the same apartment
• The maximum distance between any intern and their assigned apartment is minimized

Return the minimum possible value of the maximum distance. If it's impossible to assign all interns to apartments, return -1.

Requirements

1. Assign each intern to exactly one unique apartment
2. Minimize the maximum distance between any intern and their assigned apartment
3. Return -1 if there aren't enough apartments for all interns
4. Use a greedy approach to solve the problem efficiently

Constraints

• 1 <= interns.length <= 1000
• 1 <= flats.length <= 1000
• 1 <= interns[i], flats[i] <= 10^6
• Input arrays may not be sorted
• All positions are positive integers

Examples

Example 1:

Input: interns = [1, 3, 5], flats = [2, 4, 6, 8] Output: 1 Explanation: Assign intern at 1 to flat at 2 (distance=1), intern at 3 to flat at 4 (distance=1), intern at 5 to flat at 6 (distance=1). The maximum distance is 1.

Example 2:

Input: interns = [1, 2, 3], flats = [10, 20] Output: -1 Explanation: There are only 2 flats for 3 interns, so it's impossible to assign everyone.

Example 3:

Input: interns = [10, 20, 30], flats = [10, 20, 30, 40] Output: 0 Explanation: Each intern can be assigned to a flat at exactly their preferred location.