最小断开次数

Question

N 个城市由 N-1 条公路相连。每对相邻的城市都由双向道路连接，即

i-th 城市连接到 i+1-th 城市所有 1 <= i <= N-1，给出如下：

1 --- 2 --- 3 --- 4...............(N-1) --- N

我们得到 M 类型 (c1, c2) 的查询断开城市对 c1 和 c2。为此，我们决定 block 一些道路来满足所有这些 M 查询。

Now, we have to determine the minimum number of roads that needs to be blocked such that all queries will be served.

示例：

inputs:
 -  N = 5 // number of cities
 -  M = 2 // number of query requests
 -  C = [[1,4], [2,5]] // queries

output: 1

Approach :
 1. Block the road connecting the cities C2 and C3 and all queries will be served.
 2. Thus, the minimum roads needs to be blocked is 1.

约束：

 - 1 <= T <= 2 * 10^5  // numner of test cases
 - 2 <= N <= 2 * 10^5  // number of cities
 - 0 <= M <= 2 * 10^5  // number of queries
 - 1 <= C(i,j) <=  N  

It is guaranteed that the sum of N over T test cases doesn't exceed 10^6.
It is also guaranteed that the sum of M over T test cases doesn't exceed 10^6.

我的方法：

Solved this problem using Min-Heap, but not sure if it will work on all the edges(corner) test cases and has the optimal time/space complexities.

public int solve(int N, int M, Integer[][] c) {
    int minCuts = 0;
    if(M == 0) return 0;
    // sorting based on the start city in increasing order.
    Arrays.sort(c, (Integer[] a, Integer[] b) -> {
        return a[0] - b[0];
    });

    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    // as soon as I finds any end city in my minHeap which is less than equal to my current start city, I increment mincuts and remove all elements from the minHeap. 
    for(int i = 0; i < M ; i++) {
        int start = c[i][0];
        int end = c[i][1];

        if(!minHeap.isEmpty() && minHeap.peek() <= start) {
            minCuts += 1;
            while(!minHeap.isEmpty()) {
                minHeap.poll();
            }
        }
        minHeap.add(end);
    }

    return minCuts + 1;
}

这个方法是否有任何边缘测试用例会失败？

Answer 1

对于每个查询，都有一个（含）区间的可接受切点，因此任务是找到与所有区间相交的最小切点数。

这个问题的常用算法，你可以看到 here，是这个简单过程的优化实现：

Select最小区间结束作为切点
删除它相交的所有区间
重复直到没有更多间隔。

很容易证明它总是最优的select最小区间结束：

最小切割点必须 <= 最小区间结束，否则该区间将不会被切割。
如果一个区间与任何点<=最小区间端相交，那么它也必须与最小区间端相交。
因此最小区间端是最小切点的最佳选择。

这需要更多的工作，但你可以证明你的算法也是这个程序的实现。

首先，我们可以证明最小区间端始终是第一个从堆中弹出的，因为在我们找到大于已知端点的起点之前不会弹出任何内容。

然后我们可以证明从堆中移除的端点恰好对应于第一个端点所切割的区间。它们的所有起点都必须 <= 第一个端点，否则我们会更早地删除它们。请注意，您没有将查询调整为包含间隔，因此您的测试显示 peek() <= start。如果将它们调整为包含，则为 peek() < start.

最后，我们可以简单地证明堆上总是有未弹出的区间，所以你需要在最后 +1。

因此您的算法会生成相同的最优 select 离子切割点。不过，它比另一个更复杂，也更难验证，所以我不会使用它。

最小断开次数

Minimum number of disconnections

java

algorithm

math

heap

data-structures