452 - Minimum Number of Arrows to Burst Balloons

Find this problem here

Problem Statement

There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [x_start, x_end] denotes a balloon whose horizontal diameter stretches between x_start and x_end. You do not know the exact y-coordinates of the balloons.

Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with x_start and x_end is burst by an arrow shot at x if x_start <= x <= x_end. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.

Given the array points, return the minimum number of arrows that must be shot to burst all balloons.

Sample Inputs

Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 6, bursting the balloons [2,8] and [1,6].
- Shoot an arrow at x = 11, bursting the balloons [10,16] and [7,12].

Algorithm

We will iterate through the array, keeping a track of the low and high bounds of the interval of overlap in which we plan to take a shot. If there is overlap between the current low and high bounds and the current tuple (interval), then we will update the low and high indexes to be the innermost values, respectively. Once we detect a tuple for which there is no overlap, we will update a final answer value and set the low and high value to the current tuple’s low and high value. We will finally return the final answer value plus one (This is due to updating the final answer after we have moved on to the next interval, so we have to account for the last shot taken).

Implementation

From the outset of the problem, we know that this problem is some variant of an interval problem. We see from the sample input given to us that the input array points is not sorted. As with most interval problems, we will need to sort this array based on either points[n][0] or points[n][1] for all possible n (We’ll choose to go with points[n][1] for ease of use). We can sort based on points[n][1] easily using Java 8’s comparator compatibility Arrays.sort(points, (a, b) -> Integer.compare(a[1],b[1]));

We can also establish that we will need to keep a track of the number of shots taken. The specific locations of the shots don’t matter, so we don’t need to keep a track of these values. We can initialize a variable ans to keep track of the number of shots we’ve taken. This will be the value that we return at the end.

We also have a few option for checking overlaps between the current tuple and the current low and current high. While it is entirely possible to do this all in a one-line if statement, it is far more convenient to create a completely separate boolean function that takes in the current low value, current high value, and the current tuple. The function then does all of the relevant checks and returns. My first submission was incorrect due to an incorrect implementation of this function. I initially failed to check for the case where the interval marked by low and high was completely encompassed by the current tuple (That is, when low >= tuple[0] and high <= tuple[1]).

Solution

// Author: Ashish Jayamohan

public int findMinArrowShots(int[][] points) {
    int ans = 0;
    Arrays.sort(points, (a, b) -> Integer.compare(a[1],b[1]));
    int low = points[0][0];
    int high = points[0][1];

    for (int[] i : points) {
        if (overlap(low, high, i)) {
            low = Math.max(low, i[0]);
            high = Math.min(high, i[1]);
        }
        else {
            low = i[0];
            high = i[1];
            ans++;
        }
    }

    return ans + 1;
}

public boolean overlap(int low, int high, int[] tuple) {
    return (low <= tuple[0] && tuple[0] <= high || low <= tuple[1] && tuple[1] <= high || low >= tuple[0] && high <= tuple[1]);
}