mediumBinary SearchPattern: Binary Search on Answer

Minimum Nodes for Coverage Solution

Problem Statement

Given a set of intervals representing the coverage range of available servers, and a target number `k`, find the minimum number of servers needed such that their combined coverage spans at least `k` units. Each server `i` has a coverage interval `[start_i, end_i]`.

Examples

Example 1:

Input:{"servers":[[1,5],[2,6],[8,10],[9,12]],"k":7}

Output:2

Explanation: The lengths of the servers are: [1,5] -> 4, [2,6] -> 4, [8,10] -> 2, [9,12] -> 3. We need to find the minimum number of servers whose lengths sum up to at least k=7. By selecting servers [1, 5] (length 4) and [9, 12] (length 3), the total length is 4 + 3 = 7. This requires 2 servers. Other combinations of 2 servers, like [2, 6] (length 4) and [9, 12] (length 3), also sum to 7. It's impossible to achieve a total length of 7 with only one server, as the maximum length of a single server is 4.

Example 2:

Input:{"servers":[[0,3],[1,4],[5,7]],"k":6}

Output:2

Explanation: The lengths of the servers are: [0,3] -> 3, [1,4] -> 3, [5,7] -> 2. We need to find the minimum number of servers whose lengths sum up to at least k=6. By selecting servers [0, 3] (length 3) and [1, 4] (length 3), the total length is 3 + 3 = 6. This requires 2 servers. Selecting [0,3] and [5,7] gives 3+2=5, which is not enough. Selecting [1,4] and [5,7] gives 3+2=5, which is not enough. With only one server, the maximum length is 3, which is less than 6.

Example 3:

Input:{"servers":[[1,2],[3,4],[5,6]],"k":5}

Output:-1

Explanation: The lengths of the servers are: [1,2] -> 1, [3,4] -> 1, [5,6] -> 1. We need to find the minimum number of servers whose lengths sum up to at least k=5. The maximum total coverage we can achieve by summing the lengths of all 3 servers is 1 + 1 + 1 = 3. Since this is less than the target k=5, it's impossible to achieve the target coverage. Therefore, the output is -1.

Constraints

1 <= servers.length <= 1000
1 <= k <= 10^6
0 <= start_i < end_i <= 10^6
The sum of lengths (end_i - start_i) for all servers might not be sufficient to cover k.

Time: O(N log N) due to sorting, where N is the number of servers. Space: O(1) or O(N) depending on the sort implementation.

Sort the servers by their coverage length in descending order. Then, iterate through the sorted servers, greedily adding their coverage lengths to a running total until `k` is met or exceeded. The number of servers added is the minimum required. If `k` cannot be met even with all servers, return -1.

Run, Test & Submit Code

Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.

Solve on Interactive Workspace

Tested Solutions

def minimum_nodes_for_coverage(servers, k):
    if not servers or k == 0:
        return 0

    servers.sort(key=lambda x: x[1] - x[0], reverse=True)

    current_coverage = 0
    nodes_count = 0

    for server in servers:
        coverage_length = server[1] - server[0]
        current_coverage += coverage_length
        nodes_count += 1
        if current_coverage >= k:
            return nodes_count

    return -1