题解 | 线段重合

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

#define MAX 10001

int min_heap[MAX];
int size_heap = 0;

void swap(int a, int b) {
    int temp = min_heap[a];
    min_heap[a] = min_heap[b];
    min_heap[b] = temp;
}

void add(int x) {
    min_heap[size_heap] = x;
    int i = size_heap++;
    while (i > 0 && min_heap[i] < min_heap[(i-1)/2]) {
        swap(i, (i-1)/2);
        i = (i-1)/2;
    }
}

int pop() {
    int min_val = min_heap[0];
    swap(0, --size_heap);
    int i = 0;
    int l = 2 * i + 1;
    while (l < size_heap) {
        int best = l;
        if (l + 1 < size_heap && min_heap[l + 1] < min_heap[l]) {
            best = l + 1;
        }
        if (min_heap[best] < min_heap[i]) {
            swap(best, i);
            i = best;
            l = 2 * i + 1;
        } else {
            break;
        }
    }
    return min_val;
}

// 修正比较函数：直接比较二维数组元素
int cmp_int_arr(const void* e1, const void* e2) {
    int* arr1 = (int*)e1;  // 直接转换为int指针
    int* arr2 = (int*)e2;
    return arr1[0] - arr2[0];  // 按起点升序排列
}

int max_overlap(int arr[][2], int len) {
    size_heap = 0;  // 重置堆大小！！！重要
    
    // 按起点排序
    qsort(arr, len, sizeof(arr[0]), cmp_int_arr);
    
    int ans = 0;
    int i = 0;
    for (i = 0; i < len; i++) {
        // 移除所有终点小于当前起点的线段
        while (size_heap > 0 && min_heap[0] <= arr[i][0]) {
            pop();
        }
        add(arr[i][1]);  // 添加当前线段的终点
        if (size_heap > ans) {
            ans = size_heap;
        }
    }
    return ans;
}

int main() {
    int N;
    scanf("%d", &N);
    
    int arr[N][2];
    
    for (int i = 0; i < N; i++) {
        if (scanf("%d %d", &arr[i][0], &arr[i][1]) != 2) {
            return -1;
        }
    }
    
    int ans = max_overlap(arr, N);  // 直接使用N作为长度
    
    printf("%d\n", ans);
    return 0;
}