// 演算法 / Algorithm:
// 1) 按右端點 x_end 由小到大排序 / Sort balloons by right endpoint ascending.
// 2) 貪心掃描：箭放在當前組的最小右端點；左端點 <= 箭位置的氣球可共用此箭，
//    否則開新箭。/ Greedy scan: place an arrow at the current group's smallest
//    right endpoint; reuse it while x_start <= arrow, else open a new arrow.

#include <stdlib.h>   // 提供 qsort / provides qsort

// 比較函數：告訴 qsort 如何排序 / Comparator telling qsort how to order two balloons.
// a、b 是 void* 指向「某一列」，每列是 int[2]。/ a,b are void* pointing to one row (int[2]).
static int cmp(const void *a, const void *b) {
    // 把 void* 轉成 int* 再取第二個數（右端點 x_end）。/ Cast to int* and read index 1 (x_end).
    // (*(const int (*)[2])a) 代表「a 指向的那一列」，[1] 取右端點。
    // Here (const int (*)[2]) means "pointer to an array of 2 ints" = one row.
    int ea = (*(const int (*)[2])a)[1];   // 第一個氣球的右端點 / first balloon's x_end
    int eb = (*(const int (*)[2])b)[1];   // 第二個氣球的右端點 / second balloon's x_end
    // 用比較而非相減，避免大數相減溢位。/ Compare (not subtract) to avoid 32-bit overflow.
    if (ea < eb) return -1;               // ea 較小排前面 / ea goes first
    if (ea > eb) return  1;               // ea 較大排後面 / ea goes later
    return 0;                             // 相等 / equal
}

int findMinArrowShots(int** points, int pointsSize, int* pointsColSize) {
    // 沒有氣球就不用箭。/ No balloons means no arrows needed.
    if (pointsSize == 0) return 0;

    // 排序：把 points 的每一列（每個氣球）按右端點排好。/ Sort rows by x_end.
    // 參數：起始位址、列數、每列大小、比較函數。/ args: base, count, element size, comparator.
    qsort(points, pointsSize, sizeof(points[0]), cmp);

    int arrows = 1;                       // 至少需要一支箭 / at least one arrow is needed
    // arrowPos 記錄目前這支箭射在哪裡 = 當前組的最小右端點。
    // arrowPos = where the current arrow is shot = current group's smallest x_end.
    long arrowPos = points[0][1];         // 用 long 保險，雖然此處比較不會溢位 / long for safety

    // 從第二個氣球開始逐一檢查。/ Check each balloon starting from index 1.
    for (int i = 1; i < pointsSize; i++) {
        // points[i][0] 是這個氣球的左端點 x_start。/ points[i][0] is this balloon's x_start.
        if (points[i][0] > arrowPos) {    // 左端點超過箭位置 → 這支箭碰不到它 / arrow can't reach it
            arrows++;                      // 必須新開一支箭 / must fire a new arrow
            arrowPos = points[i][1];       // 新箭放在這個氣球的右端點 / new arrow at this x_end
        }
        // else：x_start <= arrowPos，與當前箭重疊，被同一支箭爆掉，什麼都不用做。
        // else: it overlaps the current arrow, burst for free, nothing to do.
    }

    return arrows;                         // 回傳最少箭數 / return the minimum arrow count
}