Problem

You are given a 2D integer array intervals where intervals[i] = [starti, endi] represents all the integers from starti to endi inclusively.

A containing set is an array nums where each interval from intervals has at least two integers in nums.

  • For example, if intervals = [[1,3], [3,7], [8,9]], then [1,2,4,7,8,9] and [2,3,4,8,9] are containing sets.

Return the minimum possible size of a containing set.

Examples

Example 1

1
2
3
4

Input: intervals = [[1,3],[3,7],[8,9]]
Output: 5
Explanation: let nums = [2, 3, 4, 8, 9].
It can be shown that there cannot be any containing array of size 4.

Example 2

1
2
3
4

Input: intervals = [[1,3],[1,4],[2,5],[3,5]]
Output: 3
Explanation: let nums = [2, 3, 4].
It can be shown that there cannot be any containing array of size 2.

Example 3

1
2
3
4

Input: intervals = [[1,2],[2,3],[2,4],[4,5]]
Output: 5
Explanation: let nums = [1, 2, 3, 4, 5].
It can be shown that there cannot be any containing array of size 4.

Constraints

  • 1 <= intervals.length <= 3000
  • intervals[i].length == 2
  • 0 <= starti < endi <= 10^8

Solution

Method 1 – Greedy with Sorting

Intuition

To cover each interval with at least two numbers, we can process intervals in order of their end points. By always picking the largest possible numbers at the end of each interval, we maximize the chance that these numbers will also cover future intervals, minimizing the total set size.

Approach

  1. Sort intervals by their end, and for ties, by start descending.
  2. Keep track of the last two numbers added to the set.
  3. For each interval:
    • Count how many of the last two numbers are in the interval.
    • If both are in, do nothing.
    • If only one is in, add the interval’s end.
    • If none are in, add the last two numbers in the interval (end-1, end).
  4. Return the total set size.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    int intersectionSizeTwo(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] == b[1] ? a[0] > b[0] : a[1] < b[1];
        });
        int ans = 0, last = -1, second = -1;
        for (auto& it : intervals) {
            int cnt = (last >= it[0] && last <= it[1]) + (second >= it[0] && second <= it[1]);
            if (cnt == 2) continue;
            if (cnt == 1) {
                ans++;
                second = last;
                last = it[1];
            } else {
                ans += 2;
                last = it[1];
                second = it[1] - 1;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

import "sort"
func intersectionSizeTwo(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool {
        if intervals[i][1] == intervals[j][1] {
            return intervals[i][0] > intervals[j][0]
        }
        return intervals[i][1] < intervals[j][1]
    })
    ans, last, second := 0, -1, -1
    for _, it := range intervals {
        cnt := 0
        if last >= it[0] && last <= it[1] { cnt++ }
        if second >= it[0] && second <= it[1] { cnt++ }
        if cnt == 2 {
            continue
        } else if cnt == 1 {
            ans++
            second = last
            last = it[1]
        } else {
            ans += 2
            last = it[1]
            second = it[1] - 1
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import java.util.*;
class Solution {
    public int intersectionSizeTwo(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[1] == b[1] ? b[0] - a[0] : a[1] - b[1]);
        int ans = 0, last = -1, second = -1;
        for (int[] it : intervals) {
            int cnt = 0;
            if (last >= it[0] && last <= it[1]) cnt++;
            if (second >= it[0] && second <= it[1]) cnt++;
            if (cnt == 2) continue;
            if (cnt == 1) {
                ans++;
                second = last;
                last = it[1];
            } else {
                ans += 2;
                last = it[1];
                second = it[1] - 1;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    fun intersectionSizeTwo(intervals: Array<IntArray>): Int {
        intervals.sortWith(compareBy({ it[1] }, { -it[0] }))
        var ans = 0
        var last = -1
        var second = -1
        for (it in intervals) {
            var cnt = 0
            if (last in it[0]..it[1]) cnt++
            if (second in it[0]..it[1]) cnt++
            when (cnt) {
                2 -> {}
                1 -> {
                    ans++
                    second = last
                    last = it[1]
                }
                else -> {
                    ans += 2
                    last = it[1]
                    second = it[1] - 1
                }
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def intersectionSizeTwo(self, intervals: list[list[int]]) -> int:
        intervals.sort(key=lambda x: (x[1], -x[0]))
        ans = last = second = -1
        res = 0
        for it in intervals:
            cnt = (last >= it[0] and last <= it[1]) + (second >= it[0] and second <= it[1])
            if cnt == 2:
                continue
            elif cnt == 1:
                res += 1
                second = last
                last = it[1]
            else:
                res += 2
                last = it[1]
                second = it[1] - 1
        return res
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

impl Solution {
    pub fn intersection_size_two(mut intervals: Vec<Vec<i32>>) -> i32 {
        intervals.sort_by(|a, b| a[1].cmp(&b[1]).then(b[0].cmp(&a[0])));
        let (mut last, mut second, mut ans) = (-1, -1, 0);
        for it in intervals {
            let cnt = (last >= it[0] && last <= it[1]) as i32 + (second >= it[0] && second <= it[1]) as i32;
            if cnt == 2 {
                continue;
            } else if cnt == 1 {
                ans += 1;
                second = last;
                last = it[1];
            } else {
                ans += 2;
                last = it[1];
                second = it[1] - 1;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    intersectionSizeTwo(intervals: number[][]): number {
        intervals.sort((a, b) => a[1] === b[1] ? b[0] - a[0] : a[1] - b[1]);
        let last = -1, second = -1, ans = 0;
        for (const it of intervals) {
            let cnt = 0;
            if (last >= it[0] && last <= it[1]) cnt++;
            if (second >= it[0] && second <= it[1]) cnt++;
            if (cnt === 2) continue;
            if (cnt === 1) {
                ans++;
                second = last;
                last = it[1];
            } else {
                ans += 2;
                last = it[1];
                second = it[1] - 1;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), where n = number of intervals. Sorting dominates, and each interval is processed in O(1).
  • 🧺 Space complexity: O(1), ignoring input storage, as only a few variables are used.