1024挑战赛题解

离开学校出社会工作已久，甚是怀念大学时代 ACM 的时光，偶遇组织于 10.24 举行编程挑战赛，遂前去试了一下，很幸运地也拿了点小奖，后于此简单分享。

题目描述

某客户来到我司，购买了 N 份保单，每份保单都有一个起始时间和终止时间。为了简化计算，这两个时间使用两个整数来表示，取值范围为 0 到 1,000,000,000。

例如，其中一份保单的起始时间 t=3 且终止时间 t=9，那么这份保单的有效区间则覆盖了 6 个单位时间（包含两端点）。

可是，由于个人原因，该客户想退掉其中 1 份保单，求 剩余保单能覆盖的最大单位时间总量 是多少？

输入输出格式

输入文件 input.txt：

第一行是整数 N（0 < N <= 100,000），表示接下来总共有 N 行
接下来的 N 行，每行表示一份保单的起始以及终止时间（以空格分割）
所有终止时间都是不同的

输出文件 output.txt：

输出一个数，表示退保 1 份保单后仍能得到覆盖的最大单位时间总量

示例

输入文件(input.txt)：
3
6 9
1 5
3 7

输出文件(output.txt)：
7

解释： 三份保单覆盖区间 [1,5]、[3,7]、[6,9]

最大覆盖总量 = (5-1) + (9-6) = 4 + 3 = 7
选择退掉 [3,7]（最短独立区间），剩余覆盖量最大

题目分析

要点	说明
数据规模	最多 10 万个区间
时间范围	0 到 1,000,000,000
核心考察	区间处理、动态规划思想
关键难点	如何找到"最无用"的保单

暴破解法（不可行）

假设分配 10 亿个桶，遍历所有区间… ❌ 数据量太大

正确思路

每个保单是否"有用"，取决于它的独立覆盖区域
只需计算每个保单独立拥有的区域大小
剔除独立区域最小的保单即可

解题思路

┌─────────────────────────────────────────────────────────┐
│                      算法流程                            │
├─────────────────────────────────────────────────────────┤
│                                                         │
│  1. 读取 N 个保单，计算每个保单的区间长度                │
│                                                         │
│  2. 按起点、终点递增方式进行二级排序                     │
│                                                         │
│  3. 划分不重叠的大区间（多个重叠取最小&最大值）          │
│                                                         │
│  4. 计算每个保单的独立覆盖区域                           │
│                                                         │
│  5. 找到独立区域最小的保单，剔除                         │
│                                                         │
│  6. 累加剩余保单的独立区域 = 答案                       │
│                                                         │
└─────────────────────────────────────────────────────────┘

C 语言实现

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

#define MAX_N 100000

// 区间结构体
typedef struct {
    int start;
    int end;
    int length;      // 区间长度
    int alone;       // 独立区域
} Interval;

// 比较函数：按起点排序
int cmp_start(const void *a, const void *b) {
    Interval *ia = (Interval *)a;
    Interval *ib = (Interval *)b;
    if (ia->start != ib->start) {
        return ia->start - ib->start;
    }
    return ia->end - ib->end;
}

// 读取输入
int read_input(const char *filename, Interval *intervals) {
    FILE *fp = fopen(filename, "r");
    if (!fp) {
        printf("Cannot open file: %s\n", filename);
        return -1;
    }
    
    int n;
    fscanf(fp, "%d", &n);
    
    for (int i = 0; i < n; i++) {
        fscanf(fp, "%d %d", &intervals[i].start, &intervals[i].end);
        intervals[i].length = intervals[i].end - intervals[i].start;
        intervals[i].alone = 0;
    }
    
    fclose(fp);
    return n;
}

// 计算独立区域
void calculate_alone(Interval *intervals, int n) {
    // 遍历所有区间对
    for (int i = 0; i < n; i++) {
        int start = intervals[i].start;
        int end = intervals[i].end;
        int overlap_start = -1;
        int overlap_end = -1;
        
        // 找到所有与当前区间重叠的区间
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            
            // 检测重叠：当前区间的起点在另一个区间内
            if (intervals[j].start <= start && start < intervals[j].end) {
                if (overlap_start == -1 || intervals[j].start > overlap_start) {
                    overlap_start = intervals[j].start;
                }
            }
            
            // 检测重叠：当前区间的终点在另一个区间内
            if (intervals[j].start < end && end <= intervals[j].end) {
                if (overlap_end == -1 || intervals[j].end < overlap_end) {
                    overlap_end = intervals[j].end;
                }
            }
        }
        
        // 计算独立区域
        int left_alone = 0;
        int right_alone = 0;
        
        if (overlap_start != -1) {
            left_alone = start - overlap_start;
        } else {
            left_alone = intervals[i].length;
        }
        
        if (overlap_end != -1) {
            right_alone = overlap_end - end;
        } else {
            right_alone = intervals[i].length;
        }
        
        intervals[i].alone = left_alone + right_alone;
    }
}

// 写输出
void write_output(const char *filename, long long result) {
    FILE *fp = fopen(filename, "w");
    if (!fp) {
        printf("Cannot open file: %s\n", filename);
        return;
    }
    
    fprintf(fp, "%lld\n", result);
    fclose(fp);
}

int main() {
    Interval intervals[MAX_N];
    
    // 读取输入
    int n = read_input("input.txt", intervals);
    if (n <= 0) {
        return 1;
    }
    
    // 排序
    qsort(intervals, n, sizeof(Interval), cmp_start);
    
    // 计算每个保单的独立区域
    calculate_alone(intervals, n);
    
    // 找到独立区域最小的
    int min_alone = intervals[0].alone;
    long long total_length = intervals[0].length;
    
    for (int i = 1; i < n; i++) {
        total_length += intervals[i].length;
        if (intervals[i].alone < min_alone) {
            min_alone = intervals[i].alone;
        }
    }
    
    // 结果 = 总长度 - 被剔除区间的独立区域
    long long result = total_length - min_alone;
    
    // 写输出
    write_output("output.txt", result);
    
    printf("Result: %lld\n", result);
    
    return 0;
}

优化版本（单次读入 + 动态内存）

下面的写法与上文算法一致：读入后排序，调用同样的 calculate_alone 逻辑，再把「总区间长度之和 − 最小独立覆盖」写入结果。此处用 malloc/free 取代固定栈上大数组，适合在栈空间受限的环境编译；去掉 C++ 的 new，避免混用两套语言特性。

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

#define MAX_N 100000

typedef struct {
    int start;
    int end;
    int length;
    int alone;
} Interval;

static int cmp_start(const void *a, const void *b) {
    Interval *ia = (Interval *)a;
    Interval *ib = (Interval *)b;
    return ia->start != ib->start ? ia->start - ib->start : ia->end - ib->end;
}

static void calculate_alone(Interval *intervals, int n) {
    int i, j;
    for (i = 0; i < n; i++) {
        int start = intervals[i].start;
        int end = intervals[i].end;
        int overlap_start = -1;
        int overlap_end = -1;

        for (j = 0; j < n; j++) {
            if (i == j) continue;

            if (intervals[j].start <= start && start < intervals[j].end) {
                if (overlap_start == -1 || intervals[j].start > overlap_start) {
                    overlap_start = intervals[j].start;
                }
            }

            if (intervals[j].start < end && end <= intervals[j].end) {
                if (overlap_end == -1 || intervals[j].end < overlap_end) {
                    overlap_end = intervals[j].end;
                }
            }
        }

        {
            int left_alone, right_alone;
            if (overlap_start != -1) {
                left_alone = start - overlap_start;
            } else {
                left_alone = intervals[i].length;
            }

            if (overlap_end != -1) {
                right_alone = overlap_end - end;
            } else {
                right_alone = intervals[i].length;
            }

            intervals[i].alone = left_alone + right_alone;
        }
    }
}

int main(void) {
    FILE *fin = fopen("input.txt", "r");
    FILE *fout = fopen("output.txt", "w");
    int n, i;

    if (!fin || !fout) return 1;

    fscanf(fin, "%d", &n);
    if (n <= 0 || n > MAX_N) {
        fclose(fin);
        fclose(fout);
        return 1;
    }

    Interval *intervals = (Interval *)malloc(sizeof(Interval) * (size_t)n);
    if (!intervals) {
        fclose(fin);
        fclose(fout);
        return 1;
    }

    long long total_length = 0;

    for (i = 0; i < n; i++) {
        fscanf(fin, "%d %d", &intervals[i].start, &intervals[i].end);
        intervals[i].length = intervals[i].end - intervals[i].start;
        intervals[i].alone = intervals[i].length;
        total_length += intervals[i].length;
    }
    fclose(fin);

    qsort(intervals, (size_t)n, sizeof(Interval), cmp_start);
    calculate_alone(intervals, n);

    int min_alone = intervals[0].alone;
    for (i = 1; i < n; i++) {
        if (intervals[i].alone < min_alone) {
            min_alone = intervals[i].alone;
        }
    }

    {
        long long result = total_length - min_alone;
        fprintf(fout, "%lld\n", result);
        printf("Result: %lld\n", result);
    }

    fclose(fout);
    free(intervals);
    return 0;
}

说明：比赛场景下也可继续尝试「扫描线 / 线段树」等更精细的区间结构以降低常数；本文侧重与前一版一致的思路对照。