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 pointbool 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 Codeint 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 approachdef 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 Codedef 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 pointfunction 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 caselet range = [    [3, 6], [2, 4],    [0, 2], [4, 7]];Â
console.log(intersectionSizeTwo(range)); |
Output
4
Time Complexity: O(N * log(N))
Auxiliary Space: O(N)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Information on that Topic: geeksforgeeks.org/minimum-set-size-for-covering-intervals/ […]
… [Trackback]
[…] Find More Information here to that Topic: geeksforgeeks.org/minimum-set-size-for-covering-intervals/ […]