Welcome to Subscribe On Youtube

757. Set Intersection Size At Least Two

Description

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

Solutions

• Java
• C++
• Python
• Go

• 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;
          int s = -1, e = -1;
          for (int[] v : intervals) {
              int a = v[0], b = v[1];
              if (a <= s) {
                  continue;
              }
              if (a > e) {
                  ans += 2;
                  s = b - 1;
                  e = b;
              } else {
                  ans += 1;
                  s = e;
                  e = b;
              }
          }
          return ans;
      }
  }
  

• 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[0] > b[0] : a[1] < b[1];
          });
          int ans = 0;
          int s = -1, e = -1;
          for (auto& v : intervals) {
              int a = v[0], b = v[1];
              if (a <= s) continue;
              if (a > e) {
                  ans += 2;
                  s = b - 1;
                  e = b;
              } else {
                  ans += 1;
                  s = e;
                  e = b;
              }
          }
          return ans;
      }
  };
  

• class Solution:
      def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:
          intervals.sort(key=lambda x: (x[1], -x[0]))
          s = e = -1
          ans = 0
          for a, b in intervals:
              if a <= s:
                  continue
              if a > e:
                  ans += 2
                  s, e = b - 1, b
              else:
                  ans += 1
                  s, e = e, b
          return ans
  
  

• func intersectionSizeTwo(intervals [][]int) int {
  	sort.Slice(intervals, func(i, j int) bool {
  		a, b := intervals[i], intervals[j]
  		if a[1] == b[1] {
  			return a[0] > b[0]
  		}
  		return a[1] < b[1]
  	})
  	ans := 0
  	s, e := -1, -1
  	for _, v := range intervals {
  		a, b := v[0], v[1]
  		if a <= s {
  			continue
  		}
  		if a > e {
  			ans += 2
  			s, e = b-1, b
  		} else {
  			ans += 1
  			s, e = e, b
  		}
  	}
  	return ans
  }
  

All Problems

All Solutions