Maximum length intersection of all K ranges among all given ranges

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: 0

Input: 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++

#include <bits/stdc++.h>

using namespace std;

int 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] });

}

sort(asc.begin(), asc.end());

priority_queue<int, vector<int>, greater<int> > pq;

int ans = 0;

for (int i = 0; i < n; i++) {

pq.push(asc[i].second);

while (!pq.empty() && pq.top() < asc[i].first)

pq.pop();

while (pq.size() > k)

pq.pop();

if (pq.size() == k)

ans = max(ans, pq.top() - asc[i].first + 1);

}

return ans;

}

int main()

{

int N = 5;

int K = 2;

vector<vector<int> > range = { { 5, 15 },

{ 1, 10 },

{ 14, 50 },

{ 30, 70 },

{ 99, 100 } };

cout << maxKRanges(range, K) << endl;

return 0;

}

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

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: 0

Input: 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++

#include <bits/stdc++.h>

using namespace std;

int 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] });

}

sort(asc.begin(), asc.end());

priority_queue<int, vector<int>, greater<int> > pq;

int ans = 0;

for (int i = 0; i < n; i++) {

pq.push(asc[i].second);

while (!pq.empty() && pq.top() < asc[i].first)

pq.pop();

while (pq.size() > k)

pq.pop();

if (pq.size() == k)

ans = max(ans, pq.top() - asc[i].first + 1);

}

return ans;

}

int main()

{

int N = 5;

int K = 2;

vector<vector<int> > range = { { 5, 15 },

{ 1, 10 },

{ 14, 50 },

{ 30, 70 },

{ 99, 100 } };

cout << maxKRanges(range, K) << endl;

return 0;

}

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

Read original article here

Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – admin@technoblender.com. The content will be deleted within 24 hours.

Maximum length intersection of all K ranges among all given ranges

C++

C++

Related Posts