Tap here to switch tabs
Problem
Submissions

Problem: Minimize Max Distance to Gas Station

Minimize Max Distance to Gas Station asks you to place a fixed number of new stations along a line with existing stations and return the smallest possible maximum gap between adjacent stations.

Statement

You are given an integer array, stations, representing the positions of existing gas stations along the x-axis. You are also given an integer k, indicating the number of additional gas stations you must add. These new gas stations can be placed at any position along the x-axis, including non-integer locations.

A penalty is the maximum distance between two adjacent gas stations after placing the k new stations. Your task is to return the smallest possible value of this penalty. An answer is correct if it is within 10−610^{-6} of the actual answer.

Constraints:

  • 10≤10 \leq stations.length ≤2000\leq 2000

  • 0≤0 \leq stations[i] ≤108\leq 10^8

  • The stations array is sorted in a strictly increasing order.

  • 1≤1 \leq k ≤106\leq 10^{6}

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Minimize Max Distance to Gas Station

Minimize Max Distance to Gas Station asks you to place a fixed number of new stations along a line with existing stations and return the smallest possible maximum gap between adjacent stations.

Statement

You are given an integer array, stations, representing the positions of existing gas stations along the x-axis. You are also given an integer k, indicating the number of additional gas stations you must add. These new gas stations can be placed at any position along the x-axis, including non-integer locations.

A penalty is the maximum distance between two adjacent gas stations after placing the k new stations. Your task is to return the smallest possible value of this penalty. An answer is correct if it is within 10−610^{-6} of the actual answer.

Constraints:

  • 10≤10 \leq stations.length ≤2000\leq 2000

  • 0≤0 \leq stations[i] ≤108\leq 10^8

  • The stations array is sorted in a strictly increasing order.

  • 1≤1 \leq k ≤106\leq 10^{6}