How to solve this Hackerearth Interview Problem I was not able to solve this in interview

general
1

Problem:

You are given n intervals which are termed as special intervals. Each interval is of a different type.

Again, you are given a set of q non-special intervals. For each non-special interval in the given q intervals, you have to find the number of different types of special intervals in that non-special interval.

Note: A special interval is inside a non-special interval if there exists a point x which belongs to both special interval and non-special interval.

Input format

First line: n denoting the number of special intervals

Next n lines: Two integers denoting lspecial[i] and rspecial[i] denoting the range [l,r] for the ith special interval.

Next line: q denoting the number of non-special intervals

Next q lines: Two integers denoting lnonspecial[i] and rnonspecial[i] denoting the range [l,r] for the ith non-special interval.

Output format

print q space-seperated integers denoting the answer for each of the q non-special integers.

Constraints

1<=n<=10^5

-10^9<=lspecial[i]<=10^9

-10^9<=rspecial[i]<=10^9

1<=q<= 5 * 10^4

-10^9<=lnonspecial[i]<=10^9

-10^9<=rnonspecial[i]<=10^9

Sample Input

3

1 2

1 5

1 7

3

1 3

3 3

6 7

Sample Output

3 2 1

1 Like
2

Have you got any answer for the same?

3

I know it has been ages since the problem was posted and not many solutions are out there based on this but I think this could work (C++ Code):

#include<bits/stdc++.h>
using namespace std;
/*Finds the breaking point from left intervals 
from where any left interval after this index 
point is greater than the right query value so it 
can't intersect it (return the number of rest that can't intersect it)*/
int leftEXC(int &qr,int n,int *l){
    if(qr < l[0]) return n;
    int low = 0, high = n - 1, mid;
    while(high >= low){
        mid = (low + high)/2;
        if(qr >= l[mid]) low = mid + 1;
        else if(qr >= l[mid - 1]){
            mid--;
            break;
        }
        else high = mid - 1;
    }
    return n - (mid + 1);
}
/*Finds the breaking point from right intervals 
from where any right interval after this index 
point is lesser than the left query value so it 
can't intersect it (return the number of rest that can't intersect it)*/
int rightEXC(int &ql,int n,int *r){
    if(ql > r[0]) return n;
    int low = 0, high = n - 1, mid;
    while(high >= low){
        mid = (low + high)/2;
        if(ql <= r[mid]) low = mid + 1;
        else if(ql <= r[mid - 1]){
            mid--;
            break;
        }
        else high = mid - 1;
    }
    return n - (mid + 1);
}
void solve(){
    int n, q;
    cin >> n;
    int l[n], r[n];
    for(int i=0;i<n;i++) cin >> l[i] >> r[i];
    //Sorting them to use binary search in above functions
    sort(l,l+n);
    sort(r,r+n,greater<int>());
    cin >> q;
    //Handling queries
    while(q--){
        int ql, qr;
        cin >> ql >> qr;
        cout << n - leftEXC(qr,n,l) - rightEXC(ql,n,r) << "\n";
    }
    return;
}
int main(){
    //Test-Cases
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}
/*
TC: O(Nlog(N) + Qlog(N))
SC: O(1)
*/

This works as it finds the point from which the rest of the intervals point can’t be the answer (i.e.) exclusion principle on how 2 intervals can never intersect given their bounds. Hope this helps anyone who refers to the same problem.