saint_coder's blog

How to solve this inteview problem
By saint_coder, history, 5 years ago, In English

I couldn't solve this. Please do tell me any simple approach which can pass the time constraint.

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

Time Limit 1 second

  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Hi, I guess I have found a solution, so: Let's divide special intervals that are in one non-special interval in two types: 1) starting before the left bound and ending at or after the left bound; 2) starting inside (including bounds) the non-special interval and ending somewhere (it doesn't matter, we have it inside query). Two groups do not intersect so we can count independently.

We will answer offline.

Let's count first type by using scan-line algorithm and adding the amount of opened special intervals to answer of opening now non-special intervals (so, when we meet the event like "left bound of non-special cut" we add to answer of it).

For second type we can use binsearch for sorted vector(or array) of special intervals (we have to sort by left bound). The answer is amount of intervals which have left bound in non-special interval of query (between left and right of non-special). It's easy to do using binsearch.

So, we have O((N + Q)log(N + Q)) for first types and O(Nlog(N) + Qlog(N)) for second types. The answer for interval is the sum of first type and second.

I guess it works fast enough to pass the time constraint.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There is no need to answer offline. We just need to count the intervals which overlap with [l, r]. The answer would be nothing but

    Total special intervals — intervals ending before l — intervals starting after r.

    The later 2 terms can be found in O(1) time with some obvious preprocessing

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ah, yeah, you're right, I made it a lot harder.

      → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

AlFlen I thank you man, your idea was great to implement, I am sharing the code here to any other lost souls who also want to solve this problem but couldn't due to finding it hard to implement the idea in general (Segment Tree will also work but I am not sure how to use them ;-;)

#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)
*/
→ Reply