> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/strings-arrays-and-2-pointers/max-range-queries-1.md).

# Max Range Queries

You have C=100,000 cakes, numbered 1 through C. Each cake has an integer height; initially, the height of each cake is 0.

There are N operations. In each operation, you are given two integers L and R, and you should increase by 1 the height of each of the cakes L,L+1,…,R. One of these N operations should be removed and the remaining N−1 operations are then performed.

Chef wants to remove one operation in such a way that after the remaining N−1 operations are performed, the number of cakes with height exactly K is maximum possible. Since Chef is a bit busy these days, he has asked for your help. You need to find the maximum number of cakes with height exactly K that can be achieved by removing one operation.

#### Input <a href="#input" id="input"></a>

* The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
* The first line of each test case contains two space-separated integers N and K.
* Each of the next N lines contains two space-separated integers L and R describing one operation.

#### Output <a href="#output" id="output"></a>

For each test case, print a single line containing one integer — the maximum possible number of cakes with height K.

#### Constraints <a href="#constraints" id="constraints"></a>

* 1≤T≤100
* 2≤N≤10^5
* 1≤K≤N
* 1≤L≤R≤10^5
* the sum of N over all test cases does not exceed 10^6

#### Example Input <a href="#exampleinput" id="exampleinput"></a>

```
1
3 2
2 6
4 9
1 4
```

#### Example Output <a href="#exampleoutput" id="exampleoutput"></a>

```
3
```

#### Explanation <a href="#explanation" id="explanation"></a>

**Example case 1:** Let's look at what happens after an operation is removed.

* Removing operation 11: The heights of cakes 4 through 9 increase by 1. Then, the heights of cakes 1 through 4 increase by 1. The resulting sequence of heights is \[1,1,1,2,1,1,1,1,1] (for cakes 1 through 9; the other cakes have heights 0). The number of cakes with height 2 is 1.
* Removing operation 2: The resulting sequence of heights of cakes 1 through 9 is \[1,2,2,2,1,1,0,0,0]. The number of cakes with height 2 is 3.
* Removing operation 3: The resulting sequence of heights of cakes 1 through 9 is \[0,1,1,2,2,2,1,1,1]. The number of cakes with height 2 is 3.

The maximum number of cakes with height 2 is 3.

```java
class Codechef {
    // Number of elements is fixed -> C= 1,00,000
    public static int removeQueryIndex(int[][] queries, int K) {
        // first creating our result if all the queries were used
        int[] cakes = new int[100_000];
        for (int[] query : queries) {
            // queries are 1 indexed
            cakes[query[0]] += 1;
            if (query[1] + 1 < 100_000)
                cakes[query[1] + 1] -= 1;
        }
        // Prefix count of number of cakes with height K+1 & K
        int[] numberOfKPlusOne = new int[100_000];
        int[] numberOfKs = new int[100_000];
        int Ks = 0;
        int sum = 0;
        for (int i = 0; i < 100_000; i++) {
            sum += cakes[i];
            cakes[i] = sum;
            if (cakes[i] == K) {
                numberOfKs[i] = 1 + (i > 0 ? numberOfKs[i - 1] : 0);
                Ks++;
            } else
                numberOfKs[i] = i > 0 ? numberOfKs[i - 1] : 0;

            if (cakes[i] == K + 1)
                numberOfKPlusOne[i] = 1 + (i > 0 ? numberOfKPlusOne[i - 1] : 0);
            else
                numberOfKPlusOne[i] = i > 0 ? numberOfKPlusOne[i - 1] : 0;
        }
        int max = Integer.MIN_VALUE;
        for (int[] query : queries) {
            // Finding the query with max number of K+1 & min number of K
            int numKPlusOnes = numberOfKPlusOne[query[1]] - (query[0] > 0 ? numberOfKPlusOne[query[0] - 1] : 0);
            int numKs = numberOfKs[query[1]] - (query[0] > 0 ? numberOfKs[query[0] - 1] : 0);
            max = Math.max(max, numKPlusOnes - numKs);
        }
        return Ks + max;

    }
}
```