区间问题

// LeetCode 56. 合并区间
std::vector<std::vector<int>> merge(std::vector<std::vector<int>>& iv) {
    std::sort(iv.begin(), iv.end());              // 默认按起点升序（起点相同按终点）
    std::vector<std::vector<int>> res;
    for (auto& cur : iv) {
        // 无重叠：res 为空，或 cur 的起点 > 上一段的终点 → 另起一段
        if (res.empty() || cur[0] > res.back()[1]) {
            res.push_back(cur);
        } else {                                  // 有重叠：延伸上一段的右端点
            res.back()[1] = std::max(res.back()[1], cur[1]);
        }
    }
    return res;
}

// LeetCode 57. 插入区间（原区间已按起点有序、互不重叠）
std::vector<std::vector<int>> insert(std::vector<std::vector<int>>& iv,
                                     std::vector<int> ni) {  // ni = 新区间
    std::vector<std::vector<int>> res;
    int n = iv.size(), i = 0;
    // 1) 完全在新区间左侧（无重叠）的，原样加入
    while (i < n && iv[i][1] < ni[0]) res.push_back(iv[i++]);
    // 2) 与新区间重叠的，全部合并到 ni 上
    while (i < n && iv[i][0] <= ni[1]) {
        ni[0] = std::min(ni[0], iv[i][0]);
        ni[1] = std::max(ni[1], iv[i][1]);
        i++;
    }
    res.push_back(ni);
    // 3) 完全在新区间右侧的，原样加入
    while (i < n) res.push_back(iv[i++]);
    return res;
}

// LeetCode 986. 两个有序区间列表的交集
std::vector<std::vector<int>> intervalIntersection(
        std::vector<std::vector<int>>& A, std::vector<std::vector<int>>& B) {
    std::vector<std::vector<int>> res;
    int i = 0, j = 0;
    while (i < (int)A.size() && j < (int)B.size()) {
        int lo = std::max(A[i][0], B[j][0]);       // 交集左端 = 两起点较大者
        int hi = std::min(A[i][1], B[j][1]);       // 交集右端 = 两终点较小者
        if (lo <= hi) res.push_back({lo, hi});     // lo<=hi 才真有交集
        // 谁的终点小，谁先走（它不可能再和后面产生新交集）
        if (A[i][1] < B[j][1]) i++;
        else j++;
    }
    return res;
}

// LeetCode 252. 判断能否参加所有会议（区间不重叠即可）
bool canAttendMeetings(std::vector<std::vector<int>>& iv) {
    std::sort(iv.begin(), iv.end());               // 按起点排
    for (int i = 1; i < (int)iv.size(); i++)
        if (iv[i][0] < iv[i - 1][1]) return false; // 后一个开始 < 前一个结束 → 冲突
    return true;
}

// LeetCode 253. 需要的最少会议室数量
int minMeetingRooms(std::vector<std::vector<int>>& iv) {
    std::sort(iv.begin(), iv.end());               // 按起点排
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;  // 小根堆，存各房间的结束时间
    for (auto& m : iv) {
        // 若最早结束的房间已在本会议开始前空出，复用它（弹出）
        if (!pq.empty() && pq.top() <= m[0]) pq.pop();
        pq.push(m[1]);                             // 占用一个房间（新开或复用后重新入堆）
    }
    return pq.size();                              // 堆内元素数 = 峰值同时占用房间数
}

int minMeetingRoomsSweep(std::vector<std::vector<int>>& iv) {
    std::vector<int> starts, ends;
    for (auto& m : iv) { starts.push_back(m[0]); ends.push_back(m[1]); }
    std::sort(starts.begin(), starts.end());
    std::sort(ends.begin(), ends.end());
    int rooms = 0, maxRooms = 0, j = 0;
    for (int i = 0; i < (int)starts.size(); i++) {
        // 每来一个开始事件 +1；若有会议已在此前结束则 -1（释放房间）
        while (j < (int)ends.size() && ends[j] <= starts[i]) { rooms--; j++; }
        rooms++;
        maxRooms = std::max(maxRooms, rooms);
    }
    return maxRooms;                               // 重叠峰值 = 最少会议室
}

// LeetCode 452. 用最少的箭引爆气球（气球即区间，箭是垂直线）
int findMinArrowShots(std::vector<std::vector<int>>& balloons) {
    if (balloons.empty()) return 0;
    std::sort(balloons.begin(), balloons.end(),
              [](auto& a, auto& b){ return a[1] < b[1]; });  // 按右端点升序！
    int arrows = 1, arrowX = balloons[0][1];       // 第一支箭射在第一个气球的右端点
    for (auto& b : balloons) {
        if (b[0] > arrowX) {                       // 当前气球起点越过箭的位置 → 射不到，得补一支
            arrows++;
            arrowX = b[1];                         // 新箭放在这个气球的右端点
        }
    }
    return arrows;
}

// LeetCode 1109. 航班预订统计：bookings[i] = {first, last, seats}（航班号 1..n）
std::vector<int> corpFlightBookings(std::vector<std::vector<int>>& bookings, int n) {
    std::vector<int> diff(n + 2, 0);               // 差分数组，多留一位放 r+1
    for (auto& b : bookings) {
        diff[b[0]] += b[2];                        // 区间左端 +seats
        diff[b[1] + 1] -= b[2];                    // 区间右端+1 处 -seats
    }
    std::vector<int> res(n);
    int running = 0;
    for (int i = 1; i <= n; i++) {                 // 前缀和还原每个航班的总座位
        running += diff[i];
        res[i - 1] = running;
    }
    return res;
}

// 通用扫描线：给一堆区间，求任意时刻最大重叠数（坐标可稀疏）
int maxOverlap(std::vector<std::vector<int>>& iv) {
    std::vector<std::pair<int,int>> ev;            // {坐标, 类型}，+1 进入 / -1 离开
    for (auto& x : iv) {
        ev.push_back({x[0], 1});
        ev.push_back({x[1], -1});                  // 若为闭区间且端点相接算重叠，用 x[1]+1
    }
    // 同一坐标：先处理 -1（离开）还是 +1（进入）取决于端点是否算重叠，此处离开优先
    std::sort(ev.begin(), ev.end(), [](auto& a, auto& b){
        return a.first != b.first ? a.first < b.first : a.second < b.second;
    });
    int cur = 0, best = 0;
    for (auto& [pos, d] : ev) { cur += d; best = std::max(best, cur); }
    return best;
}