Given N intervals in the form [l, r] and an integer Q. The task is to find the interval which when removed results in the coverage of the maximum number of points (Union of all the rest of the intervals). Note that all the given intervals cover numbers between 1 to Q only.
Examples:
Input: intervals[][] = {{1, 4}, {4, 5}, {5, 6}, {6, 7}, {3, 5}}, Q = 7
Output: Maximum Coverage is 7 after removing interval at index 4
When last interval is removed we are able to cover the given points using rest of the intervals
{1, 2, 3, 4, 5, 6, 7}, which is maximum coverage possible.
(The answer will also be same if we remove interval {4, 5} or {5, 6} )Input: intervals[][] = {{3, 3}, {2, 2}, {3, 4}}, Q = 4
Output: Maximum Coverage is 3 after removing interval at index 0
Approach:
- First use an array mark[] of size n + 1. If mark[i] = k, this means exactly k intervals have point i in them.
- Maintain count, total number of numbers that are covered by all the intervals.
- Now we have to iterate through all the intervals, and check if each interval is removed then how many numbers will be removed from count.
- To check new count after removal of each interval, we need to maintain an array count1[], where count1[i] tells how many numbers from 1 to i have exactly one interval in which they appear.
- New count for any interval will be count – (count1[r] – count1[l-1]). Since only those numbers which occur exactly in one interval and belong to [l, r] have to be excluded from actual count.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>#define ll long long intusing namespace std;// Function To find the required intervalvoid solve(int interval[][2], int N, int Q){ int Mark[Q] = { 0 }; for (int i = 0; i < N; i++) { int l = interval[i][0] - 1; int r = interval[i][1] - 1; for (int j = l; j <= r; j++) Mark[j]++; } // Total Count of covered numbers int count = 0; for (int i = 0; i < Q; i++) { if (Mark[i]) count++; } // Array to store numbers that occur // exactly in one interval till ith interval int count1[Q] = { 0 }; if (Mark[0] == 1) count1[0] = 1; for (int i = 1; i < Q; i++) { if (Mark[i] == 1) count1[i] = count1[i - 1] + 1; else count1[i] = count1[i - 1]; } int maxindex; int maxcoverage = 0; for (int i = 0; i < N; i++) { int l = interval[i][0] - 1; int r = interval[i][1] - 1; // Calculate New count by removing all numbers // in range [l, r] occurring exactly once int elem1; if (l != 0) elem1 = count1[r] - count1[l - 1]; else elem1 = count1[r]; if (count - elem1 >= maxcoverage) { maxcoverage = count - elem1; maxindex = i; } } cout << "Maximum Coverage is " << maxcoverage << " after removing interval at index " << maxindex;}// Driver codeint main(){ int interval[][2] = { { 1, 4 }, { 4, 5 }, { 5, 6 }, { 6, 7 }, { 3, 5 } }; int N = sizeof(interval) / sizeof(interval[0]); int Q = 7; solve(interval, N, Q); return 0;} |
Java
// Java implementation of the approachclass GFG {// Function To find the required intervalstatic void solve(int interval[][], int N, int Q){ int Mark[] = new int[Q]; for (int i = 0; i < N; i++) { int l = interval[i][0] - 1; int r = interval[i][1] - 1; for (int j = l; j <= r; j++) Mark[j]++; } // Total Count of covered numbers int count = 0; for (int i = 0; i < Q; i++) { if (Mark[i] != 0) count++; } // Array to store numbers that occur // exactly in one interval till ith interval int count1[] = new int[Q]; if (Mark[0] == 1) count1[0] = 1; for (int i = 1; i < Q; i++) { if (Mark[i] == 1) count1[i] = count1[i - 1] + 1; else count1[i] = count1[i - 1]; } int maxindex = 0; int maxcoverage = 0; for (int i = 0; i < N; i++) { int l = interval[i][0] - 1; int r = interval[i][1] - 1; // Calculate New count by removing all numbers // in range [l, r] occurring exactly once int elem1; if (l != 0) elem1 = count1[r] - count1[l - 1]; else elem1 = count1[r]; if (count - elem1 >= maxcoverage) { maxcoverage = count - elem1; maxindex = i; } } System.out.println("Maximum Coverage is " + maxcoverage + " after removing interval at index " + maxindex);}// Driver codepublic static void main(String[] args){ int interval[][] = { { 1, 4 }, { 4, 5 }, { 5, 6 }, { 6, 7 }, { 3, 5 } }; int N = interval.length; int Q = 7; solve(interval, N, Q);}}/* This code contributed by PrinciRaj1992 */ |
Python3
# Python3 implementation of the approach# Function To find the required intervaldef solve(interval, N, Q): Mark = [0 for i in range(Q)] for i in range(N): l = interval[i][0] - 1 r = interval[i][1] - 1 for j in range(l, r + 1): Mark[j] += 1 # Total Count of covered numbers count = 0 for i in range(Q): if (Mark[i]): count += 1 # Array to store numbers that occur # exactly in one interval till ith interval count1 = [0 for i in range(Q)] if (Mark[0] == 1): count1[0] = 1 for i in range(1, Q): if (Mark[i] == 1): count1[i] = count1[i - 1] + 1 else: count1[i] = count1[i - 1] maxindex = 0 maxcoverage = 0 for i in range(N): l = interval[i][0] - 1 r = interval[i][1] - 1 # Calculate New count by removing all numbers # in range [l, r] occurring exactly once elem1 = 0 if (l != 0): elem1 = count1[r] - count1[l - 1] else: elem1 = count1[r] if (count - elem1 >= maxcoverage): maxcoverage = count - elem1 maxindex = i print("Maximum Coverage is", maxcoverage, "after removing interval at index", maxindex)# Driver codeinterval = [[ 1, 4 ], [ 4, 5 ], [ 5, 6 ], [ 6, 7 ], [ 3, 5 ]]N = len(interval)Q = 7solve(interval, N, Q)# This code is contributed by mohit kumar |
C#
// C# implementation of the approachusing System;class GFG {// Function To find the required intervalstatic void solve(int[,] interval, int N, int Q){ int[] Mark = new int[Q]; for (int i = 0; i < N; i++) { int l = interval[i,0] - 1; int r = interval[i,1] - 1; for (int j = l; j <= r; j++) Mark[j]++; } // Total Count of covered numbers int count = 0; for (int i = 0; i < Q; i++) { if (Mark[i] != 0) count++; } // Array to store numbers that occur // exactly in one interval till ith interval int[] count1 = new int[Q]; if (Mark[0] == 1) count1[0] = 1; for (int i = 1; i < Q; i++) { if (Mark[i] == 1) count1[i] = count1[i - 1] + 1; else count1[i] = count1[i - 1]; } int maxindex = 0; int maxcoverage = 0; for (int i = 0; i < N; i++) { int l = interval[i,0] - 1; int r = interval[i,1] - 1; // Calculate New count by removing all numbers // in range [l, r] occurring exactly once int elem1; if (l != 0) elem1 = count1[r] - count1[l - 1]; else elem1 = count1[r]; if (count - elem1 >= maxcoverage) { maxcoverage = count - elem1; maxindex = i; } } Console.WriteLine("Maximum Coverage is " + maxcoverage + " after removing interval at index " + maxindex);}// Driver codepublic static void Main(){ int[,] interval = { { 1, 4 }, { 4, 5 }, { 5, 6 }, { 6, 7 }, { 3, 5 } }; int N = interval.Length; int Q = 7; solve(interval, N/2, Q);}}/* This code contributed by Code_Mech */ |
Javascript
<script>// Javascript implementation of the approach// Function To find the required intervalfunction solve(interval, N, Q){ var Mark = Array(Q).fill(0); for (var i = 0; i < N; i++) { var l = interval[i][0] - 1; var r = interval[i][1] - 1; for (var j = l; j <= r; j++) Mark[j]++; } // Total Count of covered numbers var count = 0; for (var i = 0; i < Q; i++) { if (Mark[i]) count++; } // Array to store numbers that occur // exactly in one interval till ith interval var count1 = Array(Q).fill(0); if (Mark[0] == 1) count1[0] = 1; for (var i = 1; i < Q; i++) { if (Mark[i] == 1) count1[i] = count1[i - 1] + 1; else count1[i] = count1[i - 1]; } var maxindex; var maxcoverage = 0; for (var i = 0; i < N; i++) { var l = interval[i][0] - 1; var r = interval[i][1] - 1; // Calculate New count by removing all numbers // in range [l, r] occurring exactly once var elem1; if (l != 0) elem1 = count1[r] - count1[l - 1]; else elem1 = count1[r]; if (count - elem1 >= maxcoverage) { maxcoverage = count - elem1; maxindex = i; } } document.write( "Maximum Coverage is " + maxcoverage + " after removing interval at index " + maxindex);}// Driver codevar interval = [ [ 1, 4 ], [ 4, 5 ], [ 5, 6 ], [ 6, 7 ], [ 3, 5 ] ];var N = interval.length;var Q = 7;solve(interval, N, Q);</script> |
Output
Maximum Coverage is 7 after removing interval at index 4
Time Complexity: O(N + Q), where N is the given size of the 2-D array and Q is the given input.
Auxiliary Space: O(Q), where Q is the given input.
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]
[…] Read More to that Topic: geeksforgeeks.org/maximum-points-covered-after-removing-an-interval/ […]
… [Trackback]
[…] Information on that Topic: geeksforgeeks.org/maximum-points-covered-after-removing-an-interval/ […]
… [Trackback]
[…] There you will find 11451 additional Information on that Topic: geeksforgeeks.org/maximum-points-covered-after-removing-an-interval/ […]
… [Trackback]
[…] Read More here on that Topic: geeksforgeeks.org/maximum-points-covered-after-removing-an-interval/ […]
… [Trackback]
[…] There you can find 34293 more Information to that Topic: geeksforgeeks.org/maximum-points-covered-after-removing-an-interval/ […]
… [Trackback]
[…] Find More here on that Topic: geeksforgeeks.org/maximum-points-covered-after-removing-an-interval/ […]