1
// Time Complexity O(Nlog(N)) - N is the number of intervals
2
// Space Complexity O(N) - N is the number of intervals, can be reduced to O(1) if needed
3
class Solution {
4
  public int intersectionSizeTwo(int[][] intervals) {
5
    // corner case: can intervals be null or empty? No
6

7
    // First, sort the intervals by end, then by reverse order start
8
    Arrays.sort(
9
        intervals,
10
        new Comparator<int[]>() {
11
          @Override
12
          public int compare(int[] a, int[] b) {
13
            if (a[1] == b[1]) {
14
              return b[0] - a[0];
15
            }
16
            return a[1] - b[1];
17
          }
18
        });
19

20
    // Second, for each two intervals, greedily find if the previous interval would satisfy next
21
    // interval's request
22
    List<Integer> list =
23
        new ArrayList<>(); // basically the ending set S, btw, we actually do not need this but I
24
    // use it here for better intuition
25

26
    // add last two nums within the range
27
    list.add(intervals[0][1] - 1);
28
    list.add(intervals[0][1]);
29

30
    for (int i = 1; i < intervals.length; i++) {
31
      int lastOne = list.get(list.size() - 1);
32
      int lastTwo = list.get(list.size() - 2);
33

34
      int[] interval = intervals[i];
35
      int start = interval[0];
36
      int end = interval[1];
37

38
      // if overlaps at least 2
39
      if (lastOne >= start && lastTwo >= start) {
40
        continue;
41
      } else if (lastOne >= start) { // if overlaps 1
42
        list.add(end);
43
      } else { // if not overlapping
44
        list.add(end - 1);
45
        list.add(end);
46
      }
47
    }
48

49
    return list.size();
50
  }
51
}