1840. Maximum Building Height

#include <stdlib.h>

// 演算法 / Algorithm:
// 1. 把 [1,0] 和（若需要）[n,∞] 加入約束，按 id 排序。
//    Add [1,0] and (if needed) [n,∞], then sort restrictions by id.
// 2. 左右兩次掃描，把每個約束收緊成真正的可達上界。
//    Two passes (left, right) tighten each cap to its real reachable bound.
// 3. 對每對相鄰約束用峰值公式 (hl+hr+d)/2 取最大。
//    For each adjacent pair, the peak is (hl+hr+d)/2; take the max.

// 每個約束存成一個結構：id 與高度都用 long 避免溢位。
// One restriction: id and height stored as long to avoid 32-bit overflow.
typedef struct { long id, h; } Pair;

// qsort 用的比較函式：依 id 由小到大排序。
// Comparator for qsort: order by id ascending.
static int cmp(const void *a, const void *b) {
    Pair *pa = (Pair *)a, *pb = (Pair *)b;        // 把 void* 轉回 Pair* / cast back to Pair*
    if (pa->id < pb->id) return -1;               // a 在前 / a comes first
    if (pa->id > pb->id) return 1;                // b 在前 / b comes first
    return 0;                                     // 相等（不會發生，id 唯一）/ equal (won't happen, ids unique)
}

long lmin(long a, long b) { return a < b ? a : b; } // 取兩個 long 的較小值 / min of two longs

int maxBuilding(int n, int** restrictions, int restrictionsSize, int* restrictionsColSize) {
    // 最多需要 原約束數 + 2 個位置（多出 [1,0] 與 [n,∞]）。
    // Need at most restrictionsSize + 2 slots (extra [1,0] and [n,∞]).
    Pair *r = (Pair *)malloc(sizeof(Pair) * (restrictionsSize + 2));
    int m = 0;                                    // m = 目前已放入的數量 / current count

    r[m].id = 1; r[m].h = 0; m++;                 // 第 1 棟固定為 0 / building 1 fixed at height 0

    int hasN = 0;                                 // 標記 n 是否已被約束 / does n already appear?
    for (int i = 0; i < restrictionsSize; i++) {  // 複製所有給定約束 / copy all given restrictions
        r[m].id = restrictions[i][0];             // restrictions[i][0] 是建築編號 / the building id
        r[m].h  = restrictions[i][1];             // restrictions[i][1] 是高度上限 / the height cap
        if (r[m].id == n) hasN = 1;               // 若剛好是最後一棟，記下 / note if it's building n
        m++;
    }
    // 若最後一棟沒被約束，加入一個「幾乎無限」的上限，讓掃描自然算出它的高度。
    // If building n isn't restricted, add a near-infinite cap so the passes compute it.
    if (!hasN) { r[m].id = n; r[m].h = 2000000000L; m++; }

    // 依 id 排序，使相鄰約束在陣列中也相鄰。
    // Sort by id so neighbors are adjacent in the array.
    qsort(r, m, sizeof(Pair), cmp);

    // 左掃：高度不能比「左鄰高度 + 兩者距離」還高（每步最多 +1）。
    // Left pass: a height can't exceed left-neighbor's height + their distance.
    for (int i = 1; i < m; i++)
        r[i].h = lmin(r[i].h, r[i-1].h + (r[i].id - r[i-1].id));

    // 右掃：同理，從右鄰往回收緊。
    // Right pass: tighten from the right neighbor likewise.
    for (int i = m - 2; i >= 0; i--)
        r[i].h = lmin(r[i].h, r[i+1].h + (r[i+1].id - r[i].id));

    // 對每對相鄰約束算峰值，取全域最大。
    // For each adjacent pair compute the peak; keep the global max.
    long best = 0;
    for (int i = 0; i + 1 < m; i++) {
        long d = r[i+1].id - r[i].id;             // 兩棟之間的距離 / distance between the two
        long peak = (r[i].h + r[i+1].h + d) / 2;  // 峰值公式，整數除法向下取整 / peak, floored
        if (peak > best) best = peak;             // 更新答案 / update answer
    }

    free(r);                                      // 釋放配置的記憶體，避免洩漏 / free heap memory
    return (int)best;                             // 結果在 int 範圍內，安全轉回 / fits in int
}

#include <vector>
#include <array>
#include <algorithm>
using namespace std;

// 演算法同 C 版 / Same algorithm as the C version:
// 加入 [1,0] 與 [n,∞] → 排序 → 左右兩掃收緊上界 → 相鄰對取峰值最大。
// Add [1,0] and [n,∞] → sort → two passes tighten bounds → max peak over adjacent pairs.

class Solution {
public:
    int maxBuilding(int n, vector<vector<int>>& restrictions) {
        // vector<array<long,2>>：每個元素是 {id, height}，用 long 防止溢位。
        // vector<array<long,2>>: each element is {id, height}; long avoids overflow.
        vector<array<long, 2>> r;
        r.reserve(restrictions.size() + 2);       // 預留空間，避免多次擴容 / reserve to avoid reallocs

        r.push_back({1, 0});                       // 第 1 棟固定為 0 / building 1 fixed at 0

        bool hasN = false;                         // n 是否已被約束 / is building n restricted?
        for (auto& res : restrictions) {           // range-for：逐一取出每條約束 / iterate each restriction
            r.push_back({res[0], res[1]});         // res[0]=id, res[1]=maxHeight
            if (res[0] == n) hasN = true;          // 記錄是否含最後一棟 / note building n
        }
        // 最後一棟若無約束，加上「近乎無限」上限讓掃描算出真正高度。
        // If n unrestricted, add a near-infinite cap so passes derive its true height.
        if (!hasN) r.push_back({(long)n, 2000000000L});

        // 用 lambda 依 id 排序；[](){} 是匿名函式，當作比較器傳給 sort。
        // Sort by id using a lambda; [](){} is an anonymous function used as comparator.
        sort(r.begin(), r.end(),
             [](const array<long,2>& a, const array<long,2>& b){ return a[0] < b[0]; });

        int m = r.size();                          // 約束總數 / total number of restrictions

        // 左掃：高度不能超過 左鄰 + 距離（每步最多差 1）。
        // Left pass: cap by left neighbor's height plus distance.
        for (int i = 1; i < m; i++)
            r[i][1] = min(r[i][1], r[i-1][1] + (r[i][0] - r[i-1][0]));

        // 右掃：同理從右鄰收緊。
        // Right pass: tighten from the right neighbor.
        for (int i = m - 2; i >= 0; i--)
            r[i][1] = min(r[i][1], r[i+1][1] + (r[i+1][0] - r[i][0]));

        // 相鄰對的峰值公式 (hl+hr+d)/2，取最大。
        // Peak (hl+hr+d)/2 for each adjacent pair; take the maximum.
        long best = 0;
        for (int i = 0; i + 1 < m; i++) {
            long d = r[i+1][0] - r[i][0];          // 兩棟距離 / distance
            best = max(best, (r[i][1] + r[i+1][1] + d) / 2); // 更新最大峰值 / update max peak
        }
        return (int)best;                          // 回傳結果 / return answer
    }
};