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

    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mayanktyagi3111.gitbook.io/interview-prep/strings-arrays-and-2-pointers/max-range-queries-1.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.