Leetcode

Set Intersection Size At Least Two

  • Time:O(n\log n)
  • Space:O(1)

C++

class Solution {
 public:
  int intersectionSizeTwo(vector<vector<int>>& intervals) {
    int ans = 0;
    int max = -1;
    int secondMax = -1;

    sort(begin(intervals), end(intervals), [](const auto& a, const auto& b) {
      return a[1] == b[1] ? a[0] > b[0] : a[1] < b[1];
    });

    for (const auto& interval : intervals) {
      const int a = interval[0];
      const int b = interval[1];
      // max and 2nd max still satisfy
      if (max >= a && secondMax >= a)
        continue;
      if (max >= a) {  // max still satisfy
        secondMax = max;
        max = b;  // add b to the set S
        ans += 1;
      } else {              // max and 2nd max can't satisfy
        max = b;            // add b to the set S
        secondMax = b - 1;  // add b - 1 to the set S
        ans += 2;
      }
    }

    return ans;
  }
};

JAVA

class Solution {
  public int intersectionSizeTwo(int[][] intervals) {
    int ans = 0;
    int max = -1;
    int secondMax = -1;

    Arrays.sort(intervals, (a, b) -> a[1] == b[1] ? b[0] - a[0] : a[1] - b[1]);

    for (int[] interval : intervals) {
      final int a = interval[0];
      final int b = interval[1];
      // max and 2nd max still satisfy
      if (max >= a && secondMax >= a)
        continue;
      if (max >= a) { // max still satisfy
        secondMax = max;
        max = b; // add b to the set S
        ans += 1;
      } else {             // max and 2nd max can't satisfy
        max = b;           // add b to the set S
        secondMax = b - 1; // add b - 1 to the set S
        ans += 2;
      }
    }

    return ans;
  }
}