Given an array of intervals[], the task is to find the minimum count of subintervals needed to cover a given time duration. Each interval represents a segment of time that starts at a specific point in time (start time) and ends at another specific point in time (end time). The intervals may overlap and have varying lengths. If it’s impossible to cover the entire duration, return -1.
Examples:
Input: Intervals[] = [[0, 1], [6, 8], [0, 2], [5, 6], [0, 4], [0, 3], [6, 7], [1, 3], [4, 7], [1, 4], [2, 5], [2, 6], [3, 4], [4, 5], [5, 7], [6, 9]], timeDuration = 9
Output: 3
Explanation: We can take subintervals [0, 4], [4, 7], and [6, 9]. There are also many subintervals but this is the maximum among them.Input: Intervals[] = [[0, 2], [4, 6], [8, 10], [1, 9], [1, 5], [5, 9]], timeDuration = 10
Output: 3
Explanation: We take the subintervals [0, 2], [8, 10], [1, 9]; a total of 3 subintervals.
Approach: This can be solved with the following idea:
Using Dynamic Programming, and sorting the intervals on the basis of the start time, we can get how many intervals it will cover if started from a particular time up to time duration.
Below are the steps involved in the implementation of the code:
- First, we sort the given intervals in non-decreasing order of their start times.
- We create a 1-D DP array dp with size time+1, where time is the given time duration.
- We initialize all elements of dp to INT_MAX – 1, except dp[0] = 0, since we can cover 0-time duration with 0 intervals.
- If the current time duration falls in any interval, we update dp[i] as min(dp[i], dp[interval[0]] + 1), where interval[0] is the start time of the interval and dp[interval[0]] + 1 means we are adding the current interval to the number of subintervals needed to cover time duration i.
- Finally, we return dp[time] if dp[time] < INT_MAX – 1, since dp[time] will store the minimum number of subintervals needed to cover the given time duration. Otherwise, we return -1, indicating that it is not possible to cover the given time duration using the given intervals.
Below is the implementation of the above idea:
C++
// C++ Implementation of code#include <bits/stdc++.h>using namespace std;// Function to find minimum subintervalsint CountSubintervals(vector<vector<int> >& Intervals, int time){ // Sort the intervals in increasing // order of start time sort(Intervals.begin(), Intervals.end()); // Create a dp table of size time + 1 vector<int> dp(time + 1, INT_MAX - 1); dp[0] = 0; for (int i = 1; i <= time; i++) { for (auto& interval : Intervals) { // If the current time value i // is within the current interval, // update the current dp cell // with the minimum value // between the current dp // cell and the dp cell of the // interval start time plus 1 if (interval[0] <= i && i <= interval[1]) { dp[i] = min(dp[i], dp[interval[0]] + 1); } } } // If the last dp cell has a value of // INT_MAX - 1, return -1, otherwise // return the value of the last dp cell return dp[time] == INT_MAX - 1 ? -1 : dp[time];}// Driver codeint main(){ vector<vector<int> > Intervals = { { 0, 1 }, { 6, 8 }, { 0, 2 }, { 5, 6 }, { 0, 4 }, { 0, 3 }, { 6, 7 }, { 1, 3 }, { 4, 7 }, { 1, 4 }, { 2, 5 }, { 2, 6 }, { 3, 4 }, { 4, 5 }, { 5, 7 }, { 6, 9 } }; int timeDuration = 9; // Function call int result = CountSubintervals(Intervals, timeDuration); cout << result << endl; return 0;} |
Java
// Java Implementation of codeimport java.util.*;class GFG { // Function to find minimum subintervals public static int CountSubintervals(List<List<Integer> > Intervals, int time) { // Sort the intervals in increasing // order of start time Collections.sort( Intervals, new Comparator<List<Integer> >() { public int compare(List<Integer> a, List<Integer> b) { return a.get(0) - b.get(0); } }); // Create a dp table of size time + 1 List<Integer> dp = new ArrayList<>(Collections.nCopies( time + 1, Integer.MAX_VALUE - 1)); dp.set(0, 0); for (int i = 1; i <= time; i++) { for (List<Integer> interval : Intervals) { // If the current time value i // is within the current interval, // update the current dp cell // with the minimum value // between the current dp // cell and the dp cell of the // interval start time plus 1 if (interval.get(0) <= i && i <= interval.get(1)) { dp.set(i, Math.min(dp.get(i), dp.get(interval.get(0)) + 1)); } } } // If the last dp cell has a value of // Integer.MAX_VALUE - 1, return -1, otherwise // return the value of the last dp cell return dp.get(time) == Integer.MAX_VALUE - 1 ? -1 : dp.get(time); } // Driver code public static void main(String[] args) { List<List<Integer> > Intervals = Arrays.asList( Arrays.asList(0, 1), Arrays.asList(6, 8), Arrays.asList(0, 2), Arrays.asList(5, 6), Arrays.asList(0, 4), Arrays.asList(0, 3), Arrays.asList(6, 7), Arrays.asList(1, 3), Arrays.asList(4, 7), Arrays.asList(1, 4), Arrays.asList(2, 5), Arrays.asList(2, 6), Arrays.asList(3, 4), Arrays.asList(4, 5), Arrays.asList(5, 7), Arrays.asList(6, 9)); int timeDuration = 9; // Function call int result = CountSubintervals(Intervals, timeDuration); System.out.println(result); }}// This code is contributed by prasad264 |
Python3
# Python Implementation of code# Function to find minimum subintervalsdef CountSubintervals(Intervals, time): # Sort the intervals in increasing # order of start time Intervals.sort() # Create a dp table of size time + 1 dp = [float('inf')] * (time + 1) dp[0] = 0 for i in range(1, time + 1): for interval in Intervals: # If the current time value i # is within the current interval, # update the current dp cell # with the minimum value # between the current dp # cell and the dp cell of the # interval start time plus 1 if interval[0] <= i and i <= interval[1]: dp[i] = min(dp[i], dp[interval[0]] + 1) # If the last dp cell has a value of # INT_MAX - 1, return -1, otherwise # return the value of the last dp cell return -1 if dp[time] == float('inf') else dp[time]# Driver codeif __name__ == '__main__': Intervals = [[0, 1], [6, 8], [0, 2], [5, 6], [0, 4], [0, 3], [6, 7], [ 1, 3], [4, 7], [1, 4], [2, 5], [2, 6], [3, 4], [4, 5], [5, 7], [6, 9]] timeDuration = 9 # Function call result = CountSubintervals(Intervals, timeDuration) print(result)# This code is contributed by Tapesh(tapeshdua420) |
C#
// C#Implementation of codeusing System;using System.Collections.Generic;using System.Linq;class Program{ // Function to find minimum subintervals static int CountSubintervals(List<List<int>> intervals, int time) { // Sort the intervals in increasing order of start time intervals.Sort((x, y) => x[0].CompareTo(y[0])); // Create a dp table of size time + 1 List<int> dp = Enumerable.Repeat(int.MaxValue - 1, time + 1).ToList(); dp[0] = 0; for (int i = 1; i <= time; i++) { foreach (var interval in intervals) { // If the current time value i is within the current interval, // update the current dp cell with the minimum value between // the current dp cell and the dp cell of the interval start time plus 1 if (interval[0] <= i && i <= interval[1]) { dp[i] = Math.Min(dp[i], dp[interval[0]] + 1); } } } // If the last dp cell has a value of int.MaxValue - 1, return -1, // otherwise return the value of the last dp cell return dp[time] == int.MaxValue - 1 ? -1 : dp[time]; } static void Main(string[] args) { List<List<int>> intervals = new List<List<int>> { new List<int>{0, 1}, new List<int>{6, 8}, new List<int>{0, 2}, new List<int>{5, 6}, new List<int>{0, 4}, new List<int>{0, 3}, new List<int>{6, 7}, new List<int>{1, 3}, new List<int>{4, 7}, new List<int>{1, 4}, new List<int>{2, 5}, new List<int>{2, 6}, new List<int>{3, 4}, new List<int>{4, 5}, new List<int>{5, 7}, new List<int>{6, 9} }; int timeDuration = 9; // Function call int result = CountSubintervals(intervals, timeDuration); Console.WriteLine(result); }} |
Javascript
function CountSubintervals(Intervals, time){ // Sort the intervals in increasing order of start time Intervals.sort((a, b) => a[0] - b[0]); // Create a dp table of size time + 1 const dp = new Array(time + 1).fill(Number.MAX_SAFE_INTEGER - 1); dp[0] = 0; for (let i = 1; i <= time; i++) { for (let interval of Intervals) { // If the current time value i is within the current interval, // update the current dp cell with the minimum value // between the current dp cell and the dp cell of the // interval start time plus 1 if (interval[0] <= i && i <= interval[1]) { dp[i] = Math.min(dp[i], dp[interval[0]] + 1); } } } // If the last dp cell has a value of Number.MAX_SAFE_INTEGER - 1, return -1, // otherwise return the value of the last dp cell return dp[time] == Number.MAX_SAFE_INTEGER - 1 ? -1 : dp[time];}// Driver codeconst Intervals = [[0, 1],[6, 8],[0, 2],[5, 6],[0, 4],[0, 3],[6, 7],[1, 3],[4, 7],[1, 4],[2, 5],[2, 6],[3, 4],[4, 5],[5, 7],[6, 9], ];const timeDuration = 9;// Function callconst result = CountSubintervals(Intervals, timeDuration);console.log(result); |
Output
3
Time Complexity: O(T*N)
Auxiliary Space: O(T)
Share your thoughts in the comments
