Minimum Number of Arrows to Burst Balloons LeetCode solution in Java

1
class Solution {
2
  public int findMinArrowShots(int[][] points) {
3

4
    int minNumArrows = 1;
5
    Arrays.sort(
6
        points,
7
        new Comparator<int[]>() {
8
          @Override
9
          public int compare(int[] i1, int[] i2) {
10
            if (i1[0] < i2[0]) return -1;
11
            else if (i1[0] > i2[0]) return 1;
12
            return 0;
13
          }
14
        });
15

16
    // This is where they will trip you up ( at the merge stage )
17
    // Wait ... do we actually have to merge here? The intervals have been sorted already
18
    // No you must merge
19
    // See if they can be merged
20
    // If mergeable - overwrite OR write into a new subintervals code ( new ArrayList )
21
    // Ok ... so first we compare (a1,a2) and then next step compare (a2,a3)
22
    // Now if (a1,a2) had an overlap -> why not make the next a2 = merged(a1,a2)?
23
    // That would do a carry over effect then
24
    int n = points.length;
25
    int[] candid = new int[2]; // always first interval anyways
26
    candid[0] = points[0][0];
27
    candid[1] = points[0][1];
28
    for (int i = 1; i < n; i++) {
29
      // System.out.printf("Current set = (%d,%d)\n", candid[0], candid[1]);
30
      int[] next = points[i];
31
      if (hasOverlap(candid, next)) {
32
        int[] merged = mergeInterval(candid, next);
33
        candid[0] = merged[0];
34
        candid[1] = merged[1];
35
      } else {
36
        candid[0] = next[0];
37
        candid[1] = next[1];
38
        minNumArrows++;
39
      }
40
    }
41

42
    return minNumArrows;
43
  }
44

45
  public boolean hasOverlap(int[] i1, int[] i2) {
46
    boolean hasOverlap = false;
47
    if (i1[0] <= i2[0] && i2[0] <= i1[1]) hasOverlap = true;
48
    if (i2[0] <= i1[0] && i1[0] <= i2[1]) hasOverlap = true;
49
    return hasOverlap;
50
  }
51

52
  public int[] mergeInterval(int[] i1, int[] i2) {
53
    int[] merged = new int[2];
54
    merged[0] = Math.max(i1[0], i2[0]);
55
    merged[1] = Math.min(i1[1], i2[1]);
56
    return merged;
57
  }
58
}