Can you help me with an algorithm or data structure to do the following efficiently?

help
,
1

You will be given ‘M’ ranges each consisting of a left limit and a right limit. Then you will be given an integer ‘n’ and you need to select those particular ranges such that

  1. for each range (L,R) L<= n <= R, or n remains inside that range.
  2. We must access the acceptable ranges in the descending order of the right limit.
    For example :
    Ranges :
    4 16
    3 18
    1 5
    integer : 10
    acceptable ranges : 4 16 and 3 18. (1,2) does not include 10.
    answer:
    3 18
    4 16
    (3 18) will come first as the right limit is greater (18 > 16).
2

Link to original Problem? :slight_smile:

3

Try storing the ranges in vector of std::pairs <int,int>
Sort them on el.second, where el is a pair in the vector
Check the range condition after accepting the input and just don’t push_back into the vector if n is out of range

4

@ssjgz I am just trying to solve the recent div 3 D2 on codeforces on my own.
https://codeforces.com/contest/1249/problem/D2

1 Like
5

That will take O(n) for each operation. Actually I need N such operations. So I need a faster way if that exists.

6

The question appears to be different from what you asked. From the first look, it appears to me that it is all about first finding overlapping segments and then selecting the ones with the most bad points, not very sure about the correctness but it can be done in O(N.logN) that is acceptable as per the given constraints.

7

Actually each operation takes O(1), and finally O(nlogn) to sort the vector.
Nevermind the problem statement is different.