Maximize 1D deliveries within distance and minimize total distance

Problem Statement

You are a delivery driver starting at position 0 on a 1D number line. You have a list of delivery locations locations (integers) and a maximum travel distance max_dist.

Each delivery requires you to visit the location and return to 0. Your total distance is the sum of the absolute values of the coordinates you visit, multiplied by 2 (to account for the round trip back to the origin). You want to:

1. Maximize the number of unique delivery locations visited.
2. Minimize the total distance traveled for that maximum number of deliveries.

Implement the function optimize_deliveries(locations, max_dist) which returns the maximum number of deliveries possible and the minimum total distance required to achieve it.

Function Signature

def optimize_deliveries(locations, max_dist) -> tuple[int, int]

Constraints

• locations length: 1 to 10^5
• locations values: -10^6 to 10^6
• max_dist: 0 to 10^9

Examples

Example 1: Input: locations = [2, -3, 5, -1], max_dist = 10 Output: (3, 8) Explanation: We can pick locations [2, -1, -3]. Total distance: 22 + 12 + 3*2 = 12 (too high). We pick the three closest locations: [-1, 2, -3]. The furthest is 3. Total distance = 3 * 2 = 6.

Example 2: Input: locations = [10, 20], max_dist = 15 Output: (1, 20) Explanation: Only one location (10) can be reached since 210 = 20 > 15 (Wait, 210=20 > 15 is false, so we can visit 10).