Problem Description
You are given a 2D integer array intervals where intervals[i] = [start_i, end_i] represents all the integers from start_i to end_i inclusively. A containing set is an array nums where each interval from intervals has at least two integers in nums. Return the minimum possible size of a containing set.
Key Insights
- Each interval must contribute at least two integers to the containing set.
- Overlapping intervals can share integers in the containing set.
- The approach involves sorting the intervals and strategically selecting integers to minimize the size of the containing set.
- A greedy strategy can be applied to ensure each interval is covered optimally.
Space and Time Complexity
Time Complexity: O(n log n) - due to sorting the intervals. Space Complexity: O(1) - since we are using a constant amount of space, not counting the input.
Solution
The solution involves sorting the intervals based on their end points. We then iterate through the sorted intervals and maintain a set of integers that form the containing set. For each interval, we check how many integers are already covered by our set. If fewer than two integers are covered, we add the necessary integers to ensure that the interval is satisfied. This greedy approach ensures that we minimize the size of the containing set while meeting the requirement for each interval.