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 mx = -1;
    int secondMax = -1;

    ranges::sort(intervals, [](const vector<int>& a, const vector<int>& 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];
      // The maximum and the second maximum still satisfy.
      if (mx >= a && secondMax >= a)
        continue;
      if (mx >= a) {  // The maximum still satisfy.
        secondMax = mx;
        mx = b;  // Add b to the set S.
        ans += 1;
      } else {              // The maximum and the second maximum can't satisfy.
        mx = 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
29
class Solution {
  public int intersectionSizeTwo(int[][] intervals) {
    int ans = 0;
    int mx = -1;
    int secondMax = -1;

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

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

    return ans;
  }
}