Given an array arr[] consisting of N ranges of the form [L, R], the task is to select K ranges such that the intersection length of the K ranges is maximum.
Examples:
Input: arr[] = {{5, 15}, {1, 10}, {14, 50}, {30, 70}, {99, 100}}, K = 2
Output: 21
Explanation: Selecting ranges (14, 50) and (30, 70) would give the maximum answer. Therefore, the maximum length intersection of above 2 ranges is (50 – 30 + 1) = 21.Input: arr[] = {{-8, 6}, {7, 9}, {-10, -5}, {-4, 5}}, K = 3
Output: 0Input: arr[] = {{1, 10}, {2, 5}, {3, 7}, {3, 4}, {3, 5}, {3, 10}, {4, 7}}, K = 3
Fig.1
Output: 5
Explanation: Selecting ranges (1, 10), (3, 7), (3, 10), which will give us the maximum length possible.
Approach: The problem can be solved based on the following idea:
Sorting ranges according to { L, R } and considering each given range as a potential starting point L to our required answer as [L, Kth largest ending point of ranges seen so far].
Follow the steps mentioned below to implement the idea:
- Use vector pair asc to store ranges in non-decreasing order of starting point l followed by ending point r.
- Traverse asc from the beginning and maintain min-heap (priority_queue) pq to store K largest ending point r of ranges seen so far.
- Discard the values from the heap if it is less than the starting point l[i] of the current range i.
- Update the answer as the maximum of previous answers we got and pq.top() – l[i] + 1.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to get maximum// intersection lengthint maxKRanges(vector<vector<int> > range, int k){ int n = range.size(); vector<pair<int, int> > asc; for (int i = 0; i < n; i++) { asc.push_back({ range[i][0], range[i][1] }); } // Sorting ranges in // non-descending order sort(asc.begin(), asc.end()); // Min-heap to store k largest ending // point of ranges seen so far priority_queue<int, vector<int>, greater<int> > pq; int ans = 0; for (int i = 0; i < n; i++) { // Ending point of ith range pq.push(asc[i].second); // Ranges having zero intersection while (!pq.empty() && pq.top() < asc[i].first) pq.pop(); // Size upto k while (pq.size() > k) pq.pop(); // Update answer if (pq.size() == k) ans = max(ans, pq.top() - asc[i].first + 1); } return ans;}// Driver Codeint main(){ // Number of ranges int N = 5; // Number of ranges selected at a time int K = 2; vector<vector<int> > range = { { 5, 15 }, { 1, 10 }, { 14, 50 }, { 30, 70 }, { 99, 100 } }; // Function call cout << maxKRanges(range, K) << endl; return 0;} |
Python3
# Python code to implement the approachimport heapq# Function to get maximum# intersection lengthdef maxKRanges(range_, k): n = len(range_) asc = [] for i in range(n): asc.append((range_[i][0], range_[i][1])) # Sorting ranges in # non-descending order asc.sort() # Min-heap to store k largest ending # point of ranges seen so far pq = [] ans = 0 for i in range(n): # Ending point of ith range heapq.heappush(pq, asc[i][1]) # Ranges having zero intersection while pq and pq[0] < asc[i][0]: heapq.heappop(pq) # Size upto k while len(pq) > k: heapq.heappop(pq) # Update answer if len(pq) == k: ans = max(ans, pq[0] - asc[i][0] + 1) return ans# Driver Code# Number of rangesN = 5# Number of ranges selected at a timeK = 2range_ = [[5, 15], [1, 10], [14, 50], [30, 70], [99, 100]]# Function callprint(maxKRanges(range_, K)) |
C#
using System;using System.Collections.Generic;using System.Linq;class Program{ static int MaxKRanges(List<List<int>> range, int k) { int n = range.Count; List<Tuple<int, int>> asc = new List<Tuple<int, int>>(); for (int i = 0; i < n; i++) { asc.Add(new Tuple<int, int>(range[i][0], range[i][1])); } // Sorting ranges in non-descending order asc.Sort(); // SortedSet to store k largest ending point of ranges seen so far SortedSet<int> pq = new SortedSet<int>(); int ans = 0; for (int i = 0; i < n; i++) { // Ending point of ith range pq.Add(asc[i].Item2); // Ranges having zero intersection while (pq.Count > 0 && pq.Min < asc[i].Item1) pq.Remove(pq.Min); // Size upto k while (pq.Count > k) pq.Remove(pq.Max); // Update answer if (pq.Count == k) ans = Math.Max(ans, pq.Min - asc[i].Item1 + 1); } return ans; } // Driver Code static void Main() { // Number of ranges int N = 5; // Number of ranges selected at a time int K = 2; List<List<int>> range = new List<List<int>>() { new List<int>(){ 5, 15 }, new List<int>(){ 1, 10 }, new List<int>(){ 14, 50 }, new List<int>(){ 30, 70 }, new List<int>(){ 99, 100 } }; // Function call Console.WriteLine(MaxKRanges(range, K)); }} |
Javascript
// Function to get maximum intersection lengthfunction maxKRanges(range, k) { const n = range.length; const asc = []; for (let i = 0; i < n; i++) { asc.push([range[i][0], range[i][1]]); } // Sorting ranges in non-descending order asc.sort((a, b) => a[0] - b[0]); // Min-heap to store k largest ending // point of ranges seen so far const pq = []; let ans = 0; for (let i = 0; i < n; i++) { // Ending point of ith range pq.push(asc[i][1]); // Ranges having zero intersection while (pq.length && pq[0] < asc[i][0]) { pq.shift(); } // Size upto k while (pq.length > k) { pq.shift(); } // Update answer if (pq.length === k) { ans = Math.max(ans, pq[0] - asc[i][0] + 1); } } return ans;}// Driver code// Number of rangesconst N = 5;// Number of ranges selected at a timeconst K = 2;const range = [[5, 15], [1, 10], [14, 50], [30, 70], [99, 100]];// Function callconsole.log(maxKRanges(range, K));// This code is contributed by Prajwal Kandekar |
Java
import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.PriorityQueue;class GFG { public static int maxKRanges(ArrayList<ArrayList<Integer>> range, int k) { int n = range.size(); int[][] asc = new int[n][2]; for (int i = 0; i < n; i++) { asc[i][0] = range.get(i).get(0); asc[i][1] = range.get(i).get(1); } // Sorting ranges in non-descending order Arrays.sort(asc, (a, b) -> a[0] - b[0]); // Min-heap to store k largest ending point of ranges seen so far PriorityQueue<Integer> pq = new PriorityQueue<>(k); int ans = 0; for (int i = 0; i < n; i++) { // Ending point of ith range pq.offer(asc[i][1]); // Ranges having zero intersection while (!pq.isEmpty() && pq.peek() < asc[i][0]) pq.poll(); // Size up to k while (pq.size() > k) pq.poll(); // Update answer if (pq.size() == k) ans = Math.max(ans, pq.peek() - asc[i][0] + 1); } return ans; } public static void main(String[] args) { // Number of ranges int N = 5; // Number of ranges selected at a time int K = 2; ArrayList<ArrayList<Integer>> range = new ArrayList<>(); range.add(new ArrayList<Integer>(Arrays.asList(5, 15))); range.add(new ArrayList<Integer>(Arrays.asList(1, 10))); range.add(new ArrayList<Integer>(Arrays.asList(14, 50))); range.add(new ArrayList<Integer>(Arrays.asList(30, 70))); range.add(new ArrayList<Integer>(Arrays.asList(99, 100))); // Function call System.out.println(maxKRanges(range, K)); }} |
Output
21
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!
Share your thoughts in the comments
