有公路N相連的城市N-1。每對相鄰的城市都由雙向道路連接，即
i-thcity 連接到i 1-thcity1 <= i <= N-1，如下所示：
1 --- 2 --- 3 --- 4...............(N-1) --- N
我們得到了M型別的查詢(c1, c2)，以切斷對城市C1和C2。為此，我們決定走block一些路來滿足所有這些M疑問。
現在，我們必須確定需要阻塞的最少道路數量，以便為所有查詢提供服務。
例子 ：
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.
我的方法：
使用Min-Heap解決了這個問題，但不確定它是否適用于所有邊（角）測驗用例并具有最佳的時間/空間復雜度。
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;
}
是否有任何邊緣測驗用例會導致此方法失敗？
uj5u.com熱心網友回復：
對于每個查詢，都有一個（包含）可接受切割點的區間，因此任務是找到與所有區間相交的最小切割點數。
您可以在此處看到此問題的常用演算法是此簡單程序的優化實作：
- 選擇最小的區間端點作為切點
- 洗掉所有相交的區間
- 重復直到沒有更多的間隔。
很容易證明選擇最小的區間端總是最優的：
- 最小切割點必須 <= 最小間隔結束，否則該間隔不會被切割。
- 如果一個區間與任何點相交<= 最小區間端點，那么它也必須與最小區間端點相交。
- 因此，最小區間端是最小切割點的最佳選擇。
這需要更多的作業，但您可以證明您的演算法也是此程序的實作。
首先，我們可以證明最小區間的端點總是第一個從堆中彈出的，因為在我們找到一個大于已知端點的起點之前，什么都不會彈出。
然后我們可以證明從堆中洗掉的端點與第一個端點切割的間隔完全對應。它們的所有起點都必須 <= 那個第一個終點，否則我們會更早地洗掉它們。請注意，您沒有將查詢調整為包含間隔，因此您的測驗顯示peek() <= start. 如果它們被調整為具有包容性，它會說peek() < start.
最后，我們可以簡單地證明堆上總是有未彈出的間隔，所以你 1在最后需要它。
因此，您的演算法對切割點進行了相同的優化選擇。不過，它比另一個更復雜，而且更難驗證，所以我不會使用它。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/382608.html
下一篇：圖中的最短路徑查詢