Skip to content

757. Set Intersection Size At Least Two 👍

  • Time: $O(\texttt{sort})$
  • Space: $O(\texttt{sort})$
 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
class Solution {
 public:
  int intersectionSizeTwo(vector<vector<int>>& intervals) {
    int ans = 0;
    int max = -1;
    int secondMax = -1;

    sort(intervals.begin(), intervals.end(), [](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;
  }
};

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