Today I have done leetcode's November LeetCoding Challenge with cpp.

November LeetCoding Challenge 20

Description

Set Intersection Size At Least Two

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.

Example 1:

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:

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:

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 <= 108

Solution

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[1] == b[1] && a[0] > b[0]);
    });
    int answer = 0;
    pair<int, int> pre = {-1, -1};
    for(auto &i : intervals) {
      if(pre.second == -1 || pre.second < i[0]) {
        answer += 2;
        pre.first = i[1] - 1;
        pre.second = i[1];
      } else if(pre.first < i[0]) {
        pre.first = pre.second;
        pre.second = i[1];
        answer += 1;
      }
    }
    return answer;
  }
};

// Accepted
// 117/117 cases passed (6 ms)
// Your runtime beats 52.92 % of cpp submissions
// Your memory usage beats 54.47 % of cpp submissions (21.8 MB)