There are N cities connected by N-1 roads. Each adjacent pair of cities is connected by bidirectional roads i.e.

• i-th city is connected to i 1-th city for all 1 <= i <= N-1, given as below:

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

We got M queries of type (c1, c2) to disconnect the pair of cities c1 and c2. For that we decided to block some roads to meet all these M queries.

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

Example :

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.

Constraints :

 - 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.

My Approach :

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;
}

Is there any any edge test-case for which this approach will fail?

CodePudding user response：

For each query, there is an (inclusive) interval of acceptable cut points, so the task is to find the minimum number of cut points that intersect all intervals.

The usual algorithm for this problem, which you can see here, is an optimized implementation of this simple procedure:

1. Select the smallest interval end as a cut point
2. Remove all the intervals that it intersects
3. Repeat until there are no more intervals.

It's easy to prove that that it's always optimal to select the smallest interval end:

• The smallest cut point must be <= the smallest interval end, because otherwise that interval won't get cut.
• If an interval intersects any point <= the smallest interval end, then it must also intersect the smallest interval end.
• The smallest interval end is therefore an optimal choice for the smallest cut point.

It takes a little more work, but you can prove that your algorithm is also an implementation of this procedure.

First, we can show that the smallest interval end is always the first one popped off the heap, because nothing is popped until we find a starting point greater than a known endpoint.

Then we can show that the endpoints removed from the heap correspond to exactly the intervals that are cut by that first endpoint. All of their start points must be <= that first endpoint, because otherwise we would have removed them earlier. Note that you didn't adjust your queries into inclusive intervals, so your test says peek() <= start. If they were adjusted to be inclusive, it would say peek() < start.

Finally, we can trivially show that there are always unpopped intervals left on the heap, so you need that 1 at the end.

So your algorithm makes the same optimal selection of cut points. It's more complicated than the other one, though, and harder to verify, so I wouldn't use it.