Minimum Number of Arrows to Burst Balloons - C Solution

1. Introduction

This post explores a fascinating problem from computational geometry and greedy algorithms, known as the "Minimum Number of Arrows to Burst Balloons". The problem involves finding the minimum number of arrows that must be shot vertically upwards to burst all balloons represented by intervals on a 2D plane.

Problem

Given a 2D integer array points where each points[i] = [xstart, xend] represents a balloon with a horizontal diameter stretching between xstart and xend, the task is to determine the minimum number of arrows that must be shot (from any point along the x-axis) to burst all balloons. An arrow can burst all balloons in its path as it travels upwards.

2. Solution Steps

1. Sort the array points based on the ending coordinates of the balloons.

2. Initialize a variable arrowPos to the end coordinate of the first balloon.

3. Iterate through the sorted balloons.

4. If the start coordinate of the current balloon is greater than arrowPos, increment the arrow count and update arrowPos to the end coordinate of the current balloon.

5. Return the total number of arrows needed.

3. Code Program

#include <stdio.h>
#include <stdlib.h>

// Comparator function for sorting intervals
int compare(const void* a, const void* b) {
    int* intervalA = *(int**)a;
    int* intervalB = *(int**)b;
    return intervalA[1] - intervalB[1];
}

// Function to find the minimum number of arrows to burst all balloons
int findMinArrowShots(int** points, int pointsSize, int* pointsColSize) {
    if (pointsSize == 0) return 0;

    // Sort the points based on the end coordinates
    qsort(points, pointsSize, sizeof(int*), compare);

    int arrows = 1;
    int arrowPos = points[0][1];

    for (int i = 1; i < pointsSize; i++) {
        if (points[i][0] > arrowPos) {
            arrows++;
            arrowPos = points[i][1];
        }
    }

    return arrows;
}

// Main function to test the findMinArrowShots function
int main() {
    int pointsSize = 4;
    int pointsColSize = 2;
    int pointsArray[4][2] = {{10, 16}, {2, 8}, {1, 6}, {7, 12}};
    int* points[4] = {pointsArray[0], pointsArray[1], pointsArray[2], pointsArray[3]};

    int result = findMinArrowShots(points, pointsSize, &pointsColSize);
    printf("Minimum arrows to burst all balloons: %d\n", result);

    return 0;
}

Output:

Minimum arrows to burst all balloons: 2

Explanation:

1. The compare function sorts the balloons based on their end coordinates.

2. The findMinArrowShots function then iterates through the sorted balloons.

3. If a balloon starts after the current arrowPos, it requires an additional arrow.

4. The function keeps track of the number of arrows needed to burst all balloons.

5. The main function demonstrates this with an example array of balloons and prints the result.