Minimum Set size for covering intervals

0 0 6 minutes read

Given an array arr[] consisting of N ranges of the form [L, R], the task is to determine the size of the smallest set that contains at least 2 integers within each interval.

Examples:

Input: arr[] = { {1, 3}, {2, 5}, {1, 4} }
Output: 2
Explanation: Interval [1, 3] contains the numbers 1, 2, 3.
Interval [2, 5] contains the numbers 2, 3, 4, 5.
Interval [1, 4] contains the numbers 1, 2, 3, 4.
Selecting set {2, 3} would be the smallest set covering all intervals.

Input: arr[] = { {3, 6}, {2, 4}, {0, 2}, {4, 7} }
Output: 4
Explanation: Possible Sets are

[0, 2], [4, 5] = 5

[1, 2], [4, 5] = 4

[0, 2], [4, 6] = 6

[1, 2], [4, 6] = 5

Optimum answer is 4 from 2nd set.

Approach: To solve the problem follow the below idea:

Sort the array according to their endpoint in ascending order, AND if two intervals have the same end, sort them according to their start point in descending order.

If there is no number in this interval being chosen before, we pick up the 2 biggest number in this interval (the biggest number have the most possibility to be used by the next interval).

If there is one number in this interval being chosen before, we pick up the biggest number in this interval.

If there are already two numbers in this interval being chosen before, we can skip this interval since the requirement has been fulfilled.

Below are the steps for the above approach:

Sort the intervals vector.
Initialize a variable say n to store the size of the input intervals vector.
Initialize a vector res with the two rightmost points of the intervals.
Iterate the sorted interval vector, for each interval, the start and end points are stored in the start and end variables.
Check if the start point of the current interval is greater than the rightmost point of the res vector, that means there is no common integer between the current interval and the previous interval, hence add the two rightmost points of the current interval to the res vector.
Check if the start point of the current interval is greater than the second last element of the res vector, that means there is only one common integer between the current interval and the previous interval, hence update the last element of the res vector with the endpoint of the current interval.
Return the size of the res vector.

Below is the implementation of the above approach:

C++

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Sort with respect to end point
bool compare(vector<int>& a, vector<int>& b)
{
    if (a[1] == b[1])
        return a[0] < b[0];
    else
        return a[1] < b[1];
}
 
int intersectionSizeTwo(vector<vector<int> >& intervals)
{
    int n = intervals.size();
 
    // Sort the array
    sort(intervals.begin(), intervals.end(), compare);
    vector<int> res;
 
    // Known two rightmost point
    // in the set/res
    res.push_back(intervals[0][1] - 1);
    res.push_back(intervals[0][1]);
 
    for (int i = 1; i < n; i++) {
 
        int start = intervals[i][0];
        int end = intervals[i][1];
 
        // Means there is no common between
        // curr interval and intervals
        // before this
        if (start > res.back()) {
            res.push_back(end - 1);
            res.push_back(end);
        }
 
        // Atleast 1 value from current
        // interval matches with previous
        // sets just add 1 max value
        else if (start > res[res.size() - 2]) {
            res.push_back(end);
        }
    }
    return res.size();
}
 
// Driver Code
int main()
{
 
    // ranges
    vector<vector<int> > range
        = { { 3, 6 }, { 2, 4 }, { 0, 2 }, { 4, 7 } };
 
    // Function Call
    cout << intersectionSizeTwo(range) << endl;
    return 0;
}

Java

/*package whatever //do not write package name here */
import java.util.*;
 
class GFG {
 
    // Sort with respect to end point
    public static int compare(List<Integer> a,
                              List<Integer> b)
    {
        if (a.get(1).equals(b.get(1))) {
            return a.get(0).compareTo(b.get(0));
        }
        else {
            return a.get(1).compareTo(b.get(1));
        }
    }
 
    public static int
    intersectionSizeTwo(List<List<Integer> > intervals)
    {
        int n = intervals.size();
 
        // Sort the array
        Collections.sort(intervals, GFG::compare);
        List<Integer> res = new ArrayList<>();
 
        // Known two rightmost point
        // in the set/res
        res.add(intervals.get(0).get(1) - 1);
        res.add(intervals.get(0).get(1));
 
        for (int i = 1; i < n; i++) {
 
            int start = intervals.get(i).get(0);
            int end = intervals.get(i).get(1);
 
            // Means there is no common between
            // curr interval and intervals
            // before this
            if (start > res.get(res.size() - 1)) {
                res.add(end - 1);
                res.add(end);
            }
 
            // Atleast 1 value from current
            // interval matches with previous
            // sets just add 1 max value
            else if (start > res.get(res.size() - 2)) {
                res.add(end);
            }
        }
        return res.size();
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // ranges
        List<List<Integer> > range = Arrays.asList(
            Arrays.asList(3, 6), Arrays.asList(2, 4),
            Arrays.asList(0, 2), Arrays.asList(4, 7));
 
        // Function Call
        System.out.println(intersectionSizeTwo(range));
    }
}

Python3

#python3 code for the above approach
def intersectionSizeTwo(intervals):
    n = len(intervals)
 
    # Custom comparison function to sort intervals based on end points and then start points
    def compare(a, b):
        if a[1] == b[1]:
            return a[0] < b[0]  # If end points are equal, sort by start points
        else:
            return a[1] < b[1]  # Otherwise, sort by end points
 
    # Sort intervals based on end points and start points
    intervals.sort(key=lambda x: (x[1], x[0]))
    res = [intervals[0][1] - 1, intervals[0][1]]  # Initialize result list with two rightmost points
 
    # Iterate through the sorted intervals
    for i in range(1, n):
        start = intervals[i][0]
        end = intervals[i][1]
 
        if start > res[-1]:  # If the current interval starts after the last rightmost point
            res.append(end - 1)
            res.append(end)
        elif start > res[-2]:  # If the current interval starts after the second-to-last rightmost point
            res.append(end)
 
    return len(res)  # Return the length of the result list, which represents the intersection size
 
# Driver Code
def main():
    # List of intervals/ranges
    ranges = [[3, 6], [2, 4], [0, 2], [4, 7]]
 
    # Function Call
    print(intersectionSizeTwo(ranges))
 
main()

C#

using System;
using System.Collections.Generic;
using System.Linq;
 
class GFG
{
    // Sort with respect to end point
    public static int Compare(List<int> a, List<int> b)
    {
        if (a[1] == b[1])
        {
            return a[0].CompareTo(b[0]);
        }
        else
        {
            return a[1].CompareTo(b[1]);
        }
    }
 
    public static int IntersectionSizeTwo(List<List<int>> intervals)
    {
        int n = intervals.Count;
 
        // Sort the array
        intervals.Sort(Compare);
        List<int> res = new List<int>();
 
        // Known two rightmost point
        // in the set/res
        res.Add(intervals[0][1] - 1);
        res.Add(intervals[0][1]);
 
        for (int i = 1; i < n; i++)
        {
 
            int start = intervals[i][0];
            int end = intervals[i][1];
 
            // Means there is no common between
            // curr interval and intervals
            // before this
            if (start > res[res.Count - 1])
            {
                res.Add(end - 1);
                res.Add(end);
            }
 
            // Atleast 1 value from current
            // interval matches with previous
            // sets just add 1 max value
            else if (start > res[res.Count - 2])
            {
                res.Add(end);
            }
        }
        return res.Count;
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        // ranges
        List<List<int>> range = new List<List<int>>
        {
            new List<int> { 3, 6 },
            new List<int> { 2, 4 },
            new List<int> { 0, 2 },
            new List<int> { 4, 7 }
        };
 
        // Function Call
        Console.WriteLine(IntersectionSizeTwo(range));
    }
}

Javascript

// Sort with respect to end point
function compare(a, b) {
    if (a[1] === b[1]) {
        return a[0] - b[0];
    } else {
        return a[1] - b[1];
    }
}
 
function intersectionSizeTwo(intervals) {
    let n = intervals.length;
     
     
    // Sort the array
    intervals.sort(compare);
    let res = [];
     
    // Known two rightmost point
    // in the set/res
    res.push(intervals[0][1] - 1);
    res.push(intervals[0][1]);
    for (let i = 1; i < n; i++) {
        let start = intervals[i][0];
        let end = intervals[i][1];
         
         
        // Means there is no common between
        // curr interval and intervals
        // before this
        if (start > res[res.length - 1]) {
            res.push(end - 1);
            res.push(end);
        }
        // Atleast 1 value from current
        // interval matches with previous
        // sets just add 1 max value
        else if (start > res[res.length - 2]) {
            res.push(end);
        }
    }
     
    // Returning length
    return res.length;
}
 
 
// Test case
let range = [
    [3, 6], [2, 4],
    [0, 2], [4, 7]
];
 
console.log(intersectionSizeTwo(range));

Output

Time Complexity: O(N * log(N))
Auxiliary Space: O(N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!