Bee Hive Problem

Problem Link

This is a custom problem without a hosted link. Problem description and code are provided directly.

Problem: Bee Hive Assignment

Problem Statement

There are N bees and N hives located at various positions on a straight line. Each bee must enter exactly one hive, and no hive can hold more than one bee. A bee can move left or right along the line, taking 1 minute per step.

Given the positions of all bees and all hives, determine the minimum number of minutes required for all bees to enter a hive.

Examples

Example 1
Input:

3  
5 -3 9  
5 8 0

Output:

3

Explanation:

• Bee at position 5 → Hive at 5 → 0 minutes

• Bee at position -3 → Hive at 0 → 3 minutes

• Bee at position 9 → Hive at 8 → 1 minute
  Max of all individual times = 3 minutes

Constraints

• 1 <= N <= 10⁵

• Positions are integers in range [-10⁹, 10⁹]

Intuition

To minimize the maximum time any bee takes, we need to pair bees and hives in an optimal way. Since positions are on a 1D line and movement cost is linear (|bee - hive|), the optimal strategy is to sort both arrays and pair the i-th bee with the i-th hive.

This greedy matching ensures the minimal maximum distance.

Approach

1. Sort the list of bee positions.

2. Sort the list of hive positions.

3. For each pair (bee[i], hive[i]), calculate the absolute difference.

4. Track the maximum of these differences.

5. Return the maximum time.

Code (Java)

import java.util.*;

public class BeesToHives {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        ArrayList<Integer> beesPositions = new ArrayList<>();
        ArrayList<Integer> hivesPositions = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            beesPositions.add(sc.nextInt());
        }

        for (int i = 0; i < n; i++) {
            hivesPositions.add(sc.nextInt());
        }

        int ans = beesToHives(n, beesPositions, hivesPositions);
        System.out.println(ans);
        sc.close();
    }

    public static int beesToHives(int n, ArrayList<Integer> beesPositions, ArrayList<Integer> hivesPositions) {
        Collections.sort(beesPositions);
        Collections.sort(hivesPositions);

        int maxTime = Integer.MIN_VALUE;

        for (int i = 0; i < n; i++) {
            int distance = Math.abs(beesPositions.get(i) - hivesPositions.get(i));
            maxTime = Math.max(maxTime, distance);
        }

        return maxTime;
    }
}

Time and Space Complexity

• Time Complexity: O(N log N)

  • Sorting both arrays takes O(N log N)

  • Pairing and max computation takes O(N)

• Space Complexity: O(N)

  • For storing positions in arrays

Dry Run

Input:

Bees = [5, -3, 9]  
Hives = [5, 8, 0]

After sorting:

• Bees = [-3, 5, 9]

• Hives = [0, 5, 8]

Pairings:

• Bee -3 ↔ Hive 0 → time = 3

• Bee 5 ↔ Hive 5 → time = 0

• Bee 9 ↔ Hive 8 → time = 1

Maximum time = 3

Conclusion

This problem showcases a classic greedy matching pattern on a 1D line where minimizing the maximum cost involves sorting and pairing elements by index. It's efficient and widely applicable to logistical and scheduling scenarios.