Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

757. Set Intersection Size At Least Two

Time: $O(n\log n)$

Space: $O(1)$

			


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 vector<int>& 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;
  }
};




			


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;
  }
}