NewSupermarkets | Topcoder Archive

Problem Statement

There are some ranches along a highway. You are given a int[] position, where position[i] is equal to the distance from the start of the highway to the i-th ranch. You are also given a int[] maxDistance, where maxDistance[i] is the maximum distance that the owners of the i-th ranch are willing to travel to get to the nearest supermarket.

Return the minimal number of supermarkets that must be constructed along the highway such that all the ranch owners will be customers of some supermarket.

Definition

Class:: NewSupermarkets
Method:: minNumber
Parameters:: int[], int[]
Returns:: int
Method signature:: int minNumber(int[] position, int[] maxDistance)
(be sure your method is public)

Notes

Two or more ranches can have equal positions.

Constraints

position will contain between 1 and 50 elements, inclusive.
Each element of position will be between 0 and 1000, inclusive.
maxDistance will contain exactly the same number of elements as position.
Each element of maxDistance will be between 0 and 1000, inclusive.

Examples

```
{0, 10}
```
```
{6, 7}
```
```
Returns: 1
```
A single supermarket at any position between 3 and 6 (inclusive) will do.
```
{2, 3, 7}
```
```
{0, 0, 0}
```
```
Returns: 3
```
We need to build a supermarket near each ranch.
```
{0, 10, 5}
```
```
{5, 5, 10}
```
```
Returns: 1
```
```
{0, 10, 20}
```
```
{5, 5, 5}
```
```
Returns: 2
```
```
{14, 14, 14}
```
```
{2, 5, 3}
```
```
Returns: 1
```
Since all the ranches are at the same location, one supermarket is enough.

{0, 12, 10, 2, 0, 1, 10, 12, 7, 9, 8}

{0, 3, 2, 4, 4, 2, 3, 2, 4, 0, 4}

Returns: 3

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.