Ninja And The Nested Ranges

The idea is to use the brute force approach. For each range in the ‘RANGES’, we will check all the other ranges whether it contains some other range and if some other range contains it. If the condition becomes true at any instant, then mark 1. Otherwise, in the end, mark 0.

Algorithm:

• Declare a vector of vectors of integers, ‘RESULT’ to store the final result.
• Declare a vector of integers, ‘RESULT1’ of size ‘N’, where ‘RESULT1[ i ]’ will store 1 if the ‘i’th range contains some other range. Initially, fill it with zeroes.
• Declare a vector of integers, ‘RESULT2’ of size ‘N’, where ‘RESULT2[ i ]’ will store 1 if the ‘i’th range is contained by some other range. Initially, fill it with zeroes.
• Run a loop for i = 0 to N - 1.
  • Declare two integer variables, ‘X’ and ‘Y’ and assign ‘RANGES[ i ][ 0 ]’ and ‘RANGES[ i ][ 1 ]’ to them, respectively.
  • Declare two boolean variables, ‘CONTAINS’ and ‘CONTAINED’. Initialize both of them by false. The ‘CONTAINS’ will be true if the ‘i’th range contains some other range and the ‘CONTAINED’ will be true if the ‘i’th range is contained by some other range.
  • Run a loop for j = 0 to N - 1.
    • If i == j, that shows that ranges are the same. Therefore,
      • Skip the below steps.
    • Else, declare two integer variables, ‘A’ and ‘B’ and assign ‘RANGES[ j ][ 0 ]’ and ‘RANGES[ j ][ 1 ]’ to them, respectively.
    • If CONTAINS == false && X <= A && Y >= B, that shows that ‘i’th range contains the ‘j’th range. Therefore,
      • Update ‘CONTAINS’ by true.
      • Update ‘RESULT1[ i ]’ by 1.
    • Else if CONTAINED == false && X >= A && Y <= B, that shows that ‘i’th range is contained by the ‘j’th range. Therefore,
      • Update ‘CONTAINED’ by true.
      • Update ‘RESULT2[ i ]’ by 1.
    • If CONTAINS == true && CONTAINED == true, that shows that ‘i’th range contains some other range and some other range also contains it. Therefore,
      • Break out of the inner loop.
• Push ‘RESULT1’ to the ‘RESULT’.
• Push ‘RESULT2’ to the ‘RESULT’
• In the end, return ‘RESULT’.

The idea is to sort the given array in ascending order by the start value of the ranges. If the start values of any two ranges are the same, then sort them in decreasing order of their end values.

After sorting, we have the following observations:

• if we traverse the array from beginning to end, any range can be contained only by any of the preceding ranges and not by the ranges after it. Also, the current range can only be contained by any preceding ranges if the maximum of the end values of the preceding ranges is not less than the end value of the current range.
• And if we traverse the array from end to the beginning, any range can only contain any of the ranges after it and not the preceding ranges. Also, the current range can only contain any ranges after it, if the minimum of the end values of the ranges after is not greater than the end value of the current range.

Algorithm:

• Declare a vector of vectors of integers, ‘RESULT’ to store the final result.
• Declare a vector of integers, ‘RESULT1’ of size ‘N’, where ‘RESULT1[ i ]’ will store 1 if the ‘i’th range contains some other range. Initially, fill it with zeroes.
• Declare a vector of integers, ‘RESULT2’ of size ‘N’, where ‘RESULT2[ i ]’ will store 1 if the ‘i’th range is contained by some other range. Initially, fill it with zeroes.
• Declare a vector of integers, ‘RESULT2’ of size ‘N’, where ‘RESULT2[ i ]’ will store 1 if the ‘i’th range is contained by some other range. Initially, fill it with zeroes.
• Declare a vector of an array of size 3, ‘ARR’, where the first, second and third value of the array will be the start value, end value and the index of the range present in ‘RANGES’.
• Run a loop for i = 0 to N - 1.
  • Push the start value, end value and the index of the ‘i’th range in ‘ARR’.
• Sort ‘ARR’ using a comparator function, ‘comp’.
• Declare an integer variable, ‘MINM’ and initialize it with ‘INT_MAX’.
• Run a loop for i = N - 1 to 0.
  • If ARR[ i ][ 1 ] >= MINM, that shows that the ‘i’th range contains some other range. Therefore,
    • Update ‘RESULT1[ ARR[ i ][ 2] ]’ by 1.
  • Else, ‘i’th range has minimum end value till now, Therefore,
    • Update ‘MINM’ by ‘ARR[ i ][ 1 ]’.
• Declare an integer variable, ‘MAXM’ and initialize it with ‘0’.
• Run a loop for i = 0 to N - 1.
  • If ARR[ i ][ 1 ]  <= MAXM, that shows that the ‘i’th range is contained by some other range. Therefore,
    • Update ‘RESULT2[ ARR[ i ][ 2] ]’ by 1.
  • Else, ‘i’th range has maximum end value till now, Therefore,
    • Update ‘MAXM’ by ‘ARR[ i ][ 1 ]’.
• Push ‘RESULT1’ to the ‘RESULT’.
• Push ‘RESULT2’ to the ‘RESULT’
• In the end, return ‘RESULT’.

Description of ‘comp’ function

This function will take two parameters:

• A1: An array of size 3 representing a range.
• A2: Another array of size 3 representing another range.

bool comp(A1, A2):

• If A1[ 0 ] == A2[ 0 ], that shows that the start values of the ‘A1’ and ‘A2’ are the same. Therefore,
  • Return A1[ 1 ] > A2[ 1 ].
• Else
  • Return A1[ 0 ] < A2[ 0 ].