Set Intersection Size At Least Two Problem


Description

LeetCode Problem 757.

You are given a 2D integer array intervals where intervals[i] = [start_i, end_i] 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.

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 <= start_i < end_i <= 10^8


Sample C++ Code

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
28
29
30
31
32
33
class Solution {
public:
    int intersectionSizeTwo(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b) {
            return a[1] < b[1] || (a[1] == b[1] && a[0] > b[0]); 
        });
        
        int n = intervals.size(), ans = 0, p1 = -1, p2 = -1;
        
        for (int i = 0; i < n; i++) {
            // current p1, p2 works for intervals[i]
            if (intervals[i][0] <= p1) 
                continue;
            
            // Neither of p1, p2 works for intervals[i]
            // replace p1, p2 by ending numbers
            if (intervals[i][0] > p2) {
                ans += 2;
                p2 = intervals[i][1];
                p1 = p2-1;
            }
            
            // only p2 works;  
            else {
                ans++;
                p1 = p2;
                p2 = intervals[i][1];
            }
        }
        
        return ans;
    }
};




Related Posts

Lemonade Change Problem

LeetCode 860. At a lemonade stand, each lemonade costs $5....

Set Intersection Size At Least Two Problem

LeetCode 757. You are given a 2D integer array intervals...

Maximum Swap Problem

LeetCode 670. You are given an integer num. You can...

Can Place Flowers Problem

LeetCode 605. You have a long flowerbed in which some...

Super Washing Machines Problem

LeetCode 517. You have n super washing machines on a...

Minimum Number Of Arrows To Burst Balloons Problem

LeetCode 452. There are some spherical balloons taped onto a...