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
32
33
34
35
class Solution {
 public:
  int intersectionSizeTwo(vector<vector<int>>& intervals) {
    int ans = 0;
    int mx = -1;
    int secondMax = -1;

    ranges::sort(intervals, ranges::less{}, [](const vector<int>& interval) {
      const int start = interval[0];
      const int end = interval[1];
      return pair<int, int>{end, -start};
    });

    for (const vector<int>& interval : intervals) {
      const int start = interval[0];
      const int end = interval[1];
      // The maximum and the second maximum still satisfy.
      if (mx >= start && secondMax >= start)
        continue;
      if (mx >= start) {
        // The maximum still satisfy.
        secondMax = mx;
        mx = end;  // Add `end` to the set.
        ans += 1;
      } else {
        // The maximum and the second maximum can't satisfy.
        mx = end;             // Add `end` to the set.
        secondMax = end - 1;  // Add `end - 1` to the set.
        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
30
31
class Solution {
  public int intersectionSizeTwo(int[][] intervals) {
    int ans = 0;
    int mx = -1;
    int secondMax = -1;

    Arrays.sort(intervals, Comparator.comparingInt((int[] interval) -> interval[1])
                               .thenComparingInt((int[] interval) -> - interval[0]));

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

    return ans;
  }
}