CSES Solutions – Nested Ranges Check
Given N ranges, the task is to determine for each range if it contains some other range and if some other range contains it. Range [a,b] contains range [c,d] if a ≤ c and d ≤ b. First print a line that describes for each range (in the input order) if it contains some other range (1) or not (0). Then print a line that describes for each range (in the input order) if some other range contains it (1) or not (0).
Example:
Input: N=4, range[]={{1, 6}, {2, 4}, {4, 8}, {3, 6}}
Output:
1 0 0 0
0 1 0 1
Explanation: The first line of the output (1 0 0 0) indicates whether each range contains some other range or not.
- Range [1, 6] contains [2, 4] and [3, 6], so its corresponding output is 1.
- Ranges [2, 4], [4, 8], and [3, 6] do not contain any other range, so their corresponding outputs are 0.
The second line of the output (0 1 0 1) indicates whether each range is contained by some other range or not.
- Range [1, 6] is not contained by any other range, so its corresponding output is 0.
- Range [2, 4] is contained by [1, 6], so its corresponding output is 1.
- Range [4, 8] is not contained by any other range, so its corresponding output is 0.
- Range [3, 6] is contained by [1, 6], so its corresponding output is 1.
Input: N=4, range[]={{2, 7}, {3, 5}, {1, 8}, {4, 6}}
Output:
1 0 1 0
1 1 0 1
Explanation: The first line of the output (1 0 1 0) indicates whether each range contains some other range or not.
- Range [2, 7] contains [3, 5] and [4, 6], so its corresponding output is 1.
- Range [3, 5] do not contain any other range, so its corresponding output is 0.
- Range [1, 8] contains all other ranges, so its corresponding output is 1.
- Range [4, 6] do not contain any other range, so its corresponding output is 0.
The second line of the output (1 1 0 1) indicates whether each range is contained by some other range or not.
- Range [2, 7] is contained by [1, 8], so its corresponding output is 1.
- Range [3, 5] is contained by [2, 7] and [1, 8], so its corresponding output is 1.
- Range [1, 8] is not contained by any other range, so its corresponding output is 0.
- Range [4, 6] is contained by [2, 7] and [1, 8], so its corresponding output is 1.
Approach: To solve the problem, follow the idea below:
The idea is to sort the ranges in ascending order based on their left end. If two ranges have the same left end, prioritize the one with the larger right end. Now, we only need to check the right end for both operations:
For the “contains” operation:
- Iterate from the right i.e from n-1 to 0. All the ranges before the current range (i.e. from i-1 to n-1) will have a left end greater than the left end of the current range. So, while traversing, if we find any right end with a value greater than the minimum right end so far, we can surely say that our current range contains that range with the minimum value of the right end as our condition is satisfied, current.left ≤ prev.left and prev.min_right ≤ current.right.
For the “contained” operation:
- iterate from the left i.e from 0 to n-1. All the ranges before the current range (i.e. from 0 to i-1) will have a left end lesser than the left end of the current range. So, while traversing, if we find any right end with a value lesser than the maximum right end so far, we can surely say that our current range is contained within that range with the maximum value of the right end as our condition is satisfied, prev.left ≤ current.left and current.right ≤ prev.max_right.
Step-by-step algorithm:
- Define a struct ranges to hold the range information (left end l, right end r, and index in), and overload the < operator for sorting.
- Take input for ranges in range[] array and initialize contains[], and contained[] of size n.
- Sort the ranges in ascending order of their left ends. If two ranges have the same left end, prioritize the one with the larger right end.
- Checks if a range contains another range by iterating from right, i.e. from n-1 to 0.
- If the right end of the current range is greater than minEnd, it contains another range.
- Mark the index of current range as in input order with 1.
- Update minEnd with minimum of minEnd and right end of current range.
- Checks if a range is contained by another range by iterating from left, i.e. from 0 to n-1.
- If the right end of the current range is less than maxEnd, it is contained by another range.
- Mark the index of current range as in input order with 1.
- Update maxEnd with maximum of maxEnd and right end of current range.
- Return the contains and contained vector.
Below is the implementation of above algorithm:
// C++ Code
#include <bits/stdc++.h>
using namespace std;
// struct to hold the range information
struct ranges {
// The left and right ends of the range and its index in
// the input order
int l, r, in;
// Overloads the < operator for sorting
bool operator<(const ranges& other) const
{
// If left ends are equal, the range with larger
// right end comes first
if (l == other.l)
return r > other.r;
// Otherwise, the range with smaller left end comes
// first
return l < other.l;
}
};
// Function to determine for each range if it contains some
// other range and if some other range contains it.
vector<vector<int> > checkrange(vector<vector<int> >& r,
int n)
{
vector<ranges> range(n);
vector<int> contains(n), contained(n);
for (int i = 0; i < n; i++) {
range[i].l = r[i][0];
range[i].r = r[i][1];
range[i].in = i;
}
// Sorts the ranges
sort(range.begin(), range.end());
// Checks if a range contains another
int minEnd = 2e9;
for (int i = n - 1; i >= 0; i--) {
// If the right end of the current range is greater
// than minEnd, it contains another
if (range[i].r >= minEnd)
contains[range[i].in] = 1;
// Update minEnd
minEnd = min(minEnd, range[i].r);
}
// Checks if a range is contained by another
int maxEnd = 0;
for (int i = 0; i < n; i++) {
// If the right end of the current range is less
// than maxEnd, it is contained by another
if (range[i].r <= maxEnd)
contained[range[i].in] = 1;
// Update maxEnd
maxEnd = max(maxEnd, range[i].r);
}
// Returns the contains and contained vector
return { contains, contained };
}
// Driver code
int main()
{
int n = 4;
// Example 1
vector<vector<int> > r
= { { 1, 6 }, { 2, 4 }, { 4, 8 }, { 3, 6 } };
vector<vector<int> > res = checkrange(r, n);
for (int i = 0; i < 2; i++) {
for (int j = 0; j < n; j++)
cout << res[i][j] << " ";
cout << endl;
}
return 0;
}
import java.util.*;
// Class to hold the range information
class Range implements Comparable<Range> {
// The left and right ends of the range and its index in
// the input order
int l, r, in;
// Constructor
public Range(int l, int r, int in) {
this.l = l;
this.r = r;
this.in = in;
}
// Overloads the compareTo method for sorting
@Override
public int compareTo(Range other) {
// If left ends are equal, the range with larger
// right end comes first
if (this.l == other.l)
return other.r - this.r;
// Otherwise, the range with smaller left end comes
// first
return this.l - other.l;
}
}
public class Main {
// Function to determine for each range if it contains some
// other range and if some other range contains it.
public static List<List<Integer>> checkRange(List<List<Integer>> r, int n) {
List<Range> range = new ArrayList<>();
List<Integer> contains = new ArrayList<>(Collections.nCopies(n, 0));
List<Integer> contained = new ArrayList<>(Collections.nCopies(n, 0));
for (int i = 0; i < n; i++) {
range.add(new Range(r.get(i).get(0), r.get(i).get(1), i));
}
// Sorts the ranges
Collections.sort(range);
// Checks if a range contains another
int minEnd = Integer.MAX_VALUE;
for (int i = n - 1; i >= 0; i--) {
// If the right end of the current range is greater
// than minEnd, it contains another
if (range.get(i).r >= minEnd)
contains.set(range.get(i).in, 1);
// Update minEnd
minEnd = Math.min(minEnd, range.get(i).r);
}
// Checks if a range is contained by another
int maxEnd = 0;
for (int i = 0; i < n; i++) {
// If the right end of the current range is less
// than maxEnd, it is contained by another
if (range.get(i).r <= maxEnd)
contained.set(range.get(i).in, 1);
// Update maxEnd
maxEnd = Math.max(maxEnd, range.get(i).r);
}
// Returns the contains and contained vector
return Arrays.asList(contains, contained);
}
// Driver code
public static void main(String[] args) {
int n = 4;
// Example 1
List<List<Integer>> r = Arrays.asList(Arrays.asList(1, 6), Arrays.asList(2, 4), Arrays.asList(4, 8), Arrays.asList(3, 6));
List<List<Integer>> res = checkRange(r, n);
for (int i = 0; i < 2; i++) {
for (int j = 0; j < n; j++)
System.out.print(res.get(i).get(j) + " ");
System.out.println();
}
}
}
# Python Code
# Function to determine for each range if it contains some
# other range and if some other range contains it.
def check_range(r, n):
# Define a class to hold the range information
class Range:
def __init__(self, l, r, inx):
self.l = l
self.r = r
self.inx = inx
# Create lists to store the results
contains = [0] * n
contained = [0] * n
# Initialize a list of Range objects
ranges = [Range(r[i][0], r[i][1], i) for i in range(n)]
# Sort the ranges based on their left ends
ranges.sort(key=lambda x: x.l)
# Checks if a range contains another
min_end = 2e9
for i in range(n - 1, -1, -1):
# If the right end of the current range is greater than min_end, it contains another
if ranges[i].r >= min_end:
contains[ranges[i].inx] = 1
# Update min_end
min_end = min(min_end, ranges[i].r)
# Checks if a range is contained by another
max_end = 0
for i in range(n):
# If the right end of the current range is less than max_end, it is contained by another
if ranges[i].r <= max_end:
contained[ranges[i].inx] = 1
# Update max_end
max_end = max(max_end, ranges[i].r)
# Return the contains and contained lists
return [contains, contained]
# Driver code
if __name__ == "__main__":
n = 4
# Example 1
r = [[1, 6], [2, 4], [4, 8], [3, 6]]
res = check_range(r, n)
for i in range(2):
for j in range(n):
print(res[i][j], end=" ")
print()
// Define a class to hold the range information
class Range {
constructor(l, r, inx) {
this.l = l;
this.r = r;
this.inx = inx;
}
}
// Function to determine for each range if it contains some
// other range and if some other range contains it.
function checkRange(r, n) {
// Create arrays to store the results
let contains = new Array(n).fill(0);
let contained = new Array(n).fill(0);
// Initialize an array of Range objects
let ranges = [];
for (let i = 0; i < n; i++) {
ranges.push(new Range(r[i][0], r[i][1], i));
}
// Sort the ranges based on their left ends
ranges.sort((a, b) => a.l - b.l);
// Checks if a range contains another
let minEnd = 2e9;
for (let i = n - 1; i >= 0; i--) {
// If the right end of the current range is greater than minEnd, it contains another
if (ranges[i].r >= minEnd) {
contains[ranges[i].inx] = 1;
}
// Update minEnd
minEnd = Math.min(minEnd, ranges[i].r);
}
// Checks if a range is contained by another
let maxEnd = 0;
for (let i = 0; i < n; i++) {
// If the right end of the current range is less than maxEnd, it is contained by another
if (ranges[i].r <= maxEnd) {
contained[ranges[i].inx] = 1;
}
// Update maxEnd
maxEnd = Math.max(maxEnd, ranges[i].r);
}
// Return the contains and contained arrays
return [contains, contained];
}
// Driver code
let n = 4;
// Example 1
let r = [[1, 6], [2, 4], [4, 8], [3, 6]];
let res = checkRange(r, n);
for (let i = 0; i < 2; i++) {
console.log(res[i].join(" "));
}
Output
1 0 0 0 0 1 0 1
Time Complexity: O(N*log(N)), where N is the size of the range.
Auxiliary Space: O(N)