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