Given two arrays start[] and end[] consisting of positive integers denoting the starting and ending points of a segment respectively, the task is to find the minimum number of integers which lies in at least one of the given segments and each segment contains at least one of them.
Examples:
Input: start[] = {1, 2, 3}, end[] = { 3, 5, 6}
Output: 3
Explanation:
All three ranges ([1, 3], [2, 5], [3, 6]) contains the integer 3.Input: start[] = {4, 1, 2, 5}, end[] = {7, 3, 5, 6}
Output: 3 6
Explanation:
Segments {1, 3} and {2, 5} are contains the integer 3.
Segments {4, 7} and {5, 6} contains the integer 6.
Mathematical formulation:
The mathematical way of describing the problem is to consider each given range of integers to be a line segment defined by two integer coordinates [ai, bi] on a line. Then the minimum number of integers required to cover each of the given range is the minimum number of points such that each segment contains at least one point.
The representation of Example 1 is shown below:
Naive approach:
The simplest way to solve the problem is to find the least value of all the starting points and maximum value of all ending points of all segments. Iterate over this range, and for each point in this range keep track of the number of segments which can be covered using this point. Use an array to store the number of segments as:
arr[point] = number of segments that can be covered using this point
- Find the maximum value in the array arr[].
- If this maximum value is equal to N, the index corresponding to this value is the point which covers all segments.
- If this maximum value is less than N, then the index corresponding to this value is a point which covers some segments.
- Repeat the steps 1 to 3 for array arr[] excluding this maximum value until the sum of all the maximum values found is equal to N.
Time Complexity: O((A-B+1)*N), where A is maximum of ending points of segments and B is the minimum of the starting points of the segments.
Auxiliary Space: O(1)
Efficient Approach:
Approach 1:
The problem can be solved efficiently by using the Greedy Technique. Follow the steps given below to solve the problem:
- Sort the segments by their end points.
- Select the point(or coordinate) corresponding to minimum end point of all segments.
- Now, All the segments whose starting point are less than this selected point and whose ending points are greater than this selected point can be covered by this point.
- Then print the minimum number of points.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// function to sort the 2D vector// on basis of second element.bool sortcol(const pair<int, int> p1, const pair<int, int> p2){ return p1.second < p2.second;}// Function to compute minimum number// of points which cover all segmentsvoid minPoints(pair<int, int> points[], int n){ // Sort the list of tuples by // their second element. sort(points, points + n, sortcol); // To store the solution vector<int> coordinates; int i = 0; // Iterate over all the segments while (i < n) { int seg = points[i].second; coordinates.push_back(seg); int p = i + 1; if (p >= n) break; // Get the start point of next segment int arrived = points[p].first; // Loop over all those segments whose // start point is less than the end // point of current segment while (seg >= arrived) { p += 1; if (p >= n) break; arrived = points[p].first; } i = p; } // Print the possible values of M for(auto point : coordinates) cout << point << " ";}// Driver codeint main(){ int n = 4; // Starting points of segments int start[] = { 4, 1, 2, 5 }; // Ending points of segments int end[] = { 7, 3, 5, 6 }; pair<int, int> points[n]; // Insert ranges in points[] for(int i = 0; i < n; i++) { points[i] = { start[i], end[i] }; } // Function call minPoints(points, n); return 0;}// This code is contributed by Kingash |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to compute minimum number// of points which cover all segmentsstatic void minPoints(int[][] points, int n){ // Sort the list of tuples by // their second element. Arrays.sort(points, (a, b) -> a[1] - b[1]); // To store the solution ArrayList<Integer> coordinates = new ArrayList<>(); int i = 0; // Iterate over all the segments while (i < n) { int seg = points[i][1]; coordinates.add(seg); int p = i + 1; if (p >= n) break; // Get the start point of next segment int arrived = points[p][0]; // Loop over all those segments whose // start point is less than the end // point of current segment while (seg >= arrived) { p += 1; if (p >= n) break; arrived = points[p][0]; } i = p; } // Print the possible values of M for(Integer point : coordinates) System.out.print(point + " ");}// Driver codepublic static void main(String[] args){ int n = 4; // Starting points of segments int[] start = { 4, 1, 2, 5 }; // Ending points of segments int[] end = { 7, 3, 5, 6 }; int[][] points = new int[n][2]; // Insert ranges in points[] for(int i = 0; i < n; i++) { points[i][0] = start[i]; points[i][1] = end[i]; } // Function call minPoints(points, n);}}// This code is contributed by offbeat |
Python3
# Python3 program for the above approach# Function to compute minimum number# of points which cover all segmentsdef minPoints(points): # Sort the list of tuples by # their second element. points.sort(key = lambda x: x[1]) # To store the solution coordinates = [] i = 0 # Iterate over all the segments while i < n: seg = points[i][1] coordinates.append(seg) p = i + 1 if p >= n: break # Get the start point of next segment arrived = points[p][0] # Loop over all those segments whose # start point is less than the end # point of current segment while seg >= arrived: p += 1 if p >= n: break arrived = points[p][0] i = p# Print the possible values of M for point in coordinates: print(point, end =" ")# Driver Coden = 4# Starting points of segmentsstart = [4, 1, 2, 5]# Ending points of segmentsend = [7, 3, 5, 6] points = []# Insert ranges in points[]for i in range(n): tu = (start[i], end[i]) points.append(tu)# Function CallminPoints(points) |
C#
// C# program for the above approachusing System;using System.Linq;using System.Collections.Generic;class GFG{ // Function to compute minimum number // of points which cover all segments static void minPoints(List<int []> points, int n) { // Sort the list of tuples by // their second element. points = points.OrderBy(p => p[1]).ToList(); // To store the solution List<int> coordinates = new List<int>(); int i = 0; // Iterate over all the segments while (i < n) { int seg = points[i][1]; coordinates.Add(seg); int p = i + 1; if (p >= n) break; // Get the start point of next segment int arrived = points[p][0]; // Loop over all those segments whose // start point is less than the end // point of current segment while (seg >= arrived) { p += 1; if (p >= n) break; arrived = points[p][0]; } i = p; } // Print the possible values of M foreach (int point in coordinates) Console.Write(point + " "); } // Driver code public static void Main(string[] args) { int n = 4; // Starting points of segments int[] start = { 4, 1, 2, 5 }; // Ending points of segments int[] end = { 7, 3, 5, 6 }; List<int []> points = new List<int []>(); // Insert ranges in points[] for(int i = 0; i < n; i++) { points.Add( new [] {start[i], end[i]}); } // Function call minPoints(points, n); }}// This code is contributed by phasing17 |
Javascript
<script>// JavaScript program for the above approach// Function to compute minimum number// of points which cover all segmentsfunction minPoints(points){ // Sort the list of tuples by // their second element. points.sort((a,b)=>a[1]-b[1]) // To store the solution let coordinates = [] let i = 0 // Iterate over all the segments while(i < n){ let seg = points[i][1] coordinates.push(seg) let p = i + 1 if(p >= n) break // Get the start point of next segment let arrived = points[p][0] // Loop over all those segments whose // start point is less than the end // point of current segment while(seg >= arrived){ p += 1 if(p >= n) break arrived = points[p][0] } i = p } // Print the possible values of M for(let point of coordinates) document.write(point," ")}// Driver Codelet n = 4// Starting points of segmentslet start = [4, 1, 2, 5]// Ending points of segmentslet end = [7, 3, 5, 6]let points = []// Insert ranges in points[]for(let i = 0; i < n; i++){ let tu = [start[i], end[i]] points.push(tu)}// Function CallminPoints(points)// This code is contributed by shinjanpatra</script> |
Output
3 6
Time Complexity: O(N*log N)
Auxiliary Space: O(N)
Approach 2: Divide and Conquer Algorithm
Another approach to solve the problem of finding the minimum number of points needed to cover a set of intervals, which uses a divide and conquer algorithm.
- The idea behind the divide and conquer algorithm is to recursively divide the intervals into two halves and find the minimum number of points needed to cover each half.
- Then, we can combine the solutions for the two halves by using a point to cover the intervals that overlap.
Follow the Below steps to solve the above approach:
- If there is only one interval, return 1.
- Divide the intervals into two halves.
- Recursively find the minimum number of points needed to cover the left and right halves.
- Initialize the minimum number of points to cover the overlapping intervals to the maximum of the two halves.
- Iterate through the left and right halves.
- If the intervals overlap, update the minimum number of points to cover the overlapping intervals.
- Return the minimum number of points to cover the overlapping intervals.
Below is the implementation of the above approach:
C++
// CPP program to find the minimum number of points needed// to cover all of the intervals using Divide Algorithm#include <bits/stdc++.h>using namespace std;int minimumPoints(vector<pair<int, int> > intervals){ sort(intervals.begin(), intervals.end(), [](pair<int, int> a, pair<int, int> b) { return a.second < b.second; }); vector<int> points; points.push_back(intervals[0].second); for (int i = 1; i < intervals.size(); i++) { if (intervals[i].first > points.back()) { points.push_back(intervals[i].second); } } return points.size();}int main(){ // Define the intervals vector<pair<int, int> > intervals = { { 1, 3 }, { 2, 4 }, { 3, 5 }, { 6, 8 } }; // Compute the minimum number of points needed to cover // the intervals and print it cout << minimumPoints(intervals) << endl; // Output: 2 intervals = { { 1, 2 }, { 3, 4 }, { 2, 5 }, { 5, 8 } }; cout << minimumPoints(intervals) << endl; // Output: 3}// This code is contributed by Susobhan Akhuli |
Java
// Java program to find the minimum number of points needed// to cover all of the intervals using Divide Algorithmimport java.util.Arrays;import java.util.Comparator;public class GFG { public static int minimumPoints(int[][] intervals) { // sort intervals by their ending point Arrays.sort(intervals, new Comparator<int[]>() { public int compare(int[] a, int[] b) { return a[1] - b[1]; } }); int[] points = new int[intervals.length]; int index = 0; points[index] = intervals[0][1]; // iterate through the intervals for (int i = 1; i < intervals.length; i++) { // if the starting point of the current interval // is greater than the ending point of the last // selected interval, add its ending point if (intervals[i][0] > points[index]) { points[++index] = intervals[i][1]; } } // return the number of points return index + 1; } public static void main(String[] args) { int[][] intervals = { { 1, 3 }, { 2, 4 }, { 3, 5 }, { 6, 8 } }; System.out.println( minimumPoints(intervals)); // Output: 2 int[][] intervals1 = { { 1, 2 }, { 3, 4 }, { 2, 5 }, { 5, 8 } }; System.out.println( minimumPoints(intervals1)); // Output: 3 }}// This code is contributed by Susobhan Akhuli |
Python3
# Python3 program to find the minimum number of points needed# to cover all of the intervals using Divide Algorithmfrom typing import List, Tupledef minimumPoints(intervals: List[Tuple[int, int]]) -> int: intervals.sort(key=lambda x: x[1]) points = [intervals[0][1]] for i in range(1, len(intervals)): if intervals[i][0] > points[-1]: points.append(intervals[i][1]) return len(points)if __name__ == "__main__": # Define the intervals intervals = [(1, 3), (2, 4), (3, 5), (6, 8)] # Compute the minimum number of points needed to cover the intervals minPoints = minimumPoints(intervals) # Print the result print(minPoints) # Output: 2 intervals = [(1, 2), (3, 4), (2, 5), (5, 8)] minPoints = minimumPoints(intervals) print(minPoints) # Output: 3# This code is contributed by Susobhan Akhuli |
C#
// C# program to find the minimum number of points needed// to cover all of the intervals using Divide Algorithmusing System;using System.Collections.Generic;using System.Linq;class GFG { public static int MinimumPoints(int[][] intervals) { // sort intervals by their ending point Array.Sort(intervals, new Comparison<int[]>( (a, b) => a[1].CompareTo(b[1]))); int[] points = new int[intervals.Length]; int index = 0; points[index] = intervals[0][1]; // iterate through the intervals for (int i = 1; i < intervals.Length; i++) { // if the starting point of the current interval // is greater than the ending point of the last // selected interval, add its ending point if (intervals[i][0] > points[index]) { points[++index] = intervals[i][1]; } } // return the number of points return index + 1; } public static void Main(string[] args) { int[][] intervals = { new[] { 1, 3 }, new[] { 2, 4 }, new[] { 3, 5 }, new[] { 6, 8 } }; Console.WriteLine( MinimumPoints(intervals)); // Output: 2 int[][] intervals1 = { new[] { 1, 2 }, new[] { 3, 4 }, new[] { 2, 5 }, new[] { 5, 8 } }; Console.WriteLine( MinimumPoints(intervals1)); // Output: 3 }}// This code is contributed by phasing17 |
Javascript
function minimumPoints(intervals) { intervals.sort((a, b) => a[1] - b[1]); const points = [intervals[0][1]]; for (let i = 1; i < intervals.length; i++) { if (intervals[i][0] > points[points.length - 1]) { points.push(intervals[i][1]); } } return points.length;}// Define the intervalslet intervals = [[1, 3], [2, 4], [3, 5], [6, 8]]; // Compute the minimum number of points needed to cover // the intervals and print itconsole.log(minimumPoints(intervals)); // Output: 2intervals = [[1, 2], [3, 4], [2, 5], [5, 8]]console.log(minimumPoints(intervals)); // Output: 3 // This code is contributed by imruhrbf8. |
Output
2 3
Complexity Analysis:
Time complexity: O(N*logN), due to the recursive nature of the algorithm, where N is the number of intervals.
Auxiliary Space: O(N), since we need to store the intervals in each recursive call.
Approach 3: Dynamic Programming
Another approach to solve the problem of finding the minimum number of integers required such that each Segment contains at least one of them, which uses a dynamic programming algorithm.
- The idea behind the dynamic programming algorithm is to iterate through the intervals and, for each interval, compute the minimum number of integers required such that each Segment contains at least one of them.
- To do this, we can use a two-dimensional array, where the first dimension represents the index of the interval and the second dimension represents the number of points.
At each step, we have two options: We can either use a new point to cover the current interval, or we can use one of the points that we have already used to cover a previous interval. If we use a new point, we need to increment the number of points by 1. If we use an existing point, we do not need to increment the number of points.
- We can compute the minimum number of points needed to cover the intervals using the following recurrence:
- dp[i][j] = min(dp[i-1][j], dp[i-1][j-1] + 1)
- The base case is when i is equal to 0, in which case dp[i][j] is equal to j.
- Using this recurrence, we can compute the minimum number of points needed to cover the intervals in O(nk) time, where n is the number of intervals and k is the maximum number of points needed to cover the intervals.
Follow the Below steps to solve the above approach:
- Sort the intervals by their starting point.
- Initialize a list minPoints with the length of the intervals, and set all elements to 1.
- Iterate through the intervals from the second to the last.
- For each interval, iterate through the minPoints list from the first element to the current interval.
- If the ending point of the previous interval is greater than or equal to the starting point of the current interval, update the current element of minPoints as the minimum of itself and the previous element plus 1.
- Return the last element of minPoints.
Below is the implementation of the above approach:
C++
// CPP program to find the minimum number of points needed// to cover all of the intervals using DP#include <bits/stdc++.h>using namespace std;int minimumPoints(vector<pair<int, int> > intervals){ // Sort the intervals by their starting point sort(intervals.begin(), intervals.end()); // Number of intervals int n = intervals.size(); // Initialize a list minPoints with value 1 // and size with length of the intervals vector<int> minPoints(n, 1); // Iterate through the intervals from // the second to the last for (int i = 1; i < n; i++) // For each interval, iterate through // the minPoints list from the first // element to the current interval for (int j = 0; j < i; j++) { // If the ending point of the // previous interval is greater // than or equal to the starting // point of the current interval, // update the current element // of minPoints if (intervals[j].second <= intervals[i].first) minPoints[i] = max(minPoints[i], minPoints[j] + 1); else minPoints[i] = 1; } // Return the last element of minPoints return minPoints[n - 1];}int main(){ // Define the intervals vector<pair<int, int> > intervals = { { 1, 3 }, { 2, 4 }, { 3, 5 }, { 6, 8 } }; // Compute the minimum number of points needed to cover // the intervals and print it cout << minimumPoints(intervals) << endl; // Output: 2 intervals = { { 1, 2 }, { 3, 4 }, { 2, 5 }, { 5, 8 } }; cout << minimumPoints(intervals) << endl; // Output: 3}// This code is contributed by Susobhan Akhuli |
Java
// Java program to find the minimum number of points needed// to cover all of the intervals using DPimport java.util.Arrays;import java.util.Comparator;public class GFG { public static int minimumPoints(int[][] intervals) { // sort intervals by their starting point Arrays.sort(intervals, new Comparator<int[]>() { public int compare(int[] a, int[] b) { return a[0] - b[0]; } }); // Number of intervals int n = intervals.length; // Initialize a list minPoints with value 1 // and size with length of the intervals int[] minPoints = new int[n]; Arrays.fill(minPoints, 1); // Iterate through the intervals from // the second to the last for (int i = 1; i < n; i++) { // For each interval, iterate through // the minPoints list from the first // element to the current interval for (int j = 0; j < i; j++) { // If the ending point of the // previous interval is greater // than or equal to the starting // point of the current interval, // update the current element // of minPoints if (intervals[j][1] <= intervals[i][0]) minPoints[i] = Math.max( minPoints[i], minPoints[j] + 1); else minPoints[i] = 1; } } // Return the last element of minPoints return minPoints[n - 1]; } public static void main(String[] args) { int[][] intervals = { { 1, 3 }, { 2, 4 }, { 3, 5 }, { 6, 8 } }; // Compute the minimum number of points needed to cover // the intervals and print it System.out.println( minimumPoints(intervals)); // Output: 2 int[][] intervals1 = { { 1, 2 }, { 3, 4 }, { 2, 5 }, { 5, 8 } }; System.out.println( minimumPoints(intervals1)); // Output: 3 }}// This code is contributed by Susobhan Akhuli |
Python3
# Python3 program to find the minimum number of points needed# to cover all of the intervals using DPfrom typing import List, Tupledef minimumPoints(intervals: List[Tuple[int, int]]) -> int: # Sort the intervals by their starting point intervals.sort(key=lambda x: x[0]) # Number of intervals n = len(intervals) # Initialize a list minPoints with value 1 # and size with length of the intervals minPoints = [1] * n # Iterate through the intervals from # the second to the last for i in range(1, n): # For each interval, iterate through # the minPoints list from the first # element to the current interval for j in range(i): # If the ending point of the # previous interval is greater # than or equal to the starting # point of the current interval, # update the current element # of minPoints if intervals[j][1] <= intervals[i][0]: minPoints[i] = max(minPoints[i], minPoints[j] + 1) else: minPoints[i] = 1 # Return the last element of minPoints return minPoints[-1]if __name__ == "__main__": # Define the intervals intervals = [(1, 3), (2, 4), (3, 5), (6, 8)] # Compute the minimum number of points needed to cover the intervals minPoints = minimumPoints(intervals) print(minPoints) # Output: 2 intervals = [(1, 2), (3, 4), (2, 5), (5, 8)] minPoints = minimumPoints(intervals) print(minPoints) # Output: 3# This code is contributed by Susobhan Akhuli |
C#
// C# program to find the minimum number of points needed// to cover all of the intervals using DPusing System;using System.Collections.Generic;using System.Linq;class GFG { static int MinimumPoints(List<Tuple<int, int> > intervals) { // Sort the intervals by their starting point intervals = intervals.OrderBy(t => t.Item1).ToList(); // Number of intervals int n = intervals.Count; // Initialize a list minPoints with value 1 // and size with length of the intervals List<int> minPoints = Enumerable.Repeat(1, n).ToList(); // Iterate through the intervals from // the second to the last for (int i = 1; i < n; i++) { // For each interval, iterate through // the minPoints list from the first // element to the current interval for (int j = 0; j < i; j++) { // If the ending point of the // previous interval is greater // than or equal to the starting // point of the current interval, // update the current element // of minPoints if (intervals[j].Item2 <= intervals[i].Item1) minPoints[i] = Math.Max( minPoints[i], minPoints[j] + 1); else minPoints[i] = 1; } } // Return the last element of minPoints return minPoints[n - 1]; } static void Main(string[] args) { // Define the intervals List<Tuple<int, int> > intervals = new List<Tuple<int, int> >() { Tuple.Create(1, 3), Tuple.Create(2, 4), Tuple.Create(3, 5), Tuple.Create(6, 8) }; // Compute the minimum number of points needed to // cover the intervals and print it Console.WriteLine( MinimumPoints(intervals)); // Output: 2 intervals = new List<Tuple<int, int> >() { Tuple.Create(1, 2), Tuple.Create(3, 4), Tuple.Create(2, 5), Tuple.Create(5, 8) }; Console.WriteLine( MinimumPoints(intervals)); // Output: 3 }} |
Javascript
// JavaScript program to find the minimum number of points// needed to cover all of the intervals using DP// Function to find the minimum number of points// needed to cover all of the intervalsfunction minimumPoints(intervals){ // Sort the intervals by their starting point intervals.sort((a, b) => a[0] - b[0]); // Number of intervals const n = intervals.length; // Initialize an array minPoints with value 1 // and length with the number of intervals const minPoints = new Array(n).fill(1); // Iterate through the intervals from // the second to the last for (let i = 1; i < n; i++) { // For each interval, iterate through // the minPoints array from the first // element to the current interval for (let j = 0; j < i; j++) { // If the ending point of the // previous interval is greater // than or equal to the starting // point of the current interval, // update the current element // of minPoints if (intervals[j][1] <= intervals[i][0]) { minPoints[i] = Math.max(minPoints[i], minPoints[j] + 1); } else { minPoints[i] = 1; } } } // Return the last element of minPoints return minPoints[n - 1];}// Define the intervalsconst intervals = [ [ 1, 3 ], [ 2, 4 ], [ 3, 5 ], [ 6, 8 ],];// Compute the minimum number of points needed to cover// the intervals and print itconsole.log(minimumPoints(intervals)); // Output: 2const intervals2 = [ [ 1, 2 ], [ 3, 4 ], [ 2, 5 ], [ 5, 8 ],];// Compute the minimum number of points needed to cover// the intervals and print itconsole.log(minimumPoints(intervals2)); // Output: 3 |
Output
2 3
Complexity Analysis:
Time complexity: O(N2), due to the nested loops, where N is the number of intervals.
Auxiliary Space: O(N), since we need to store the minPoints list.
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!
