By

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

10.24挑战赛题解

题目描述：

某客户来到我司，购买了N份保单，每份保单都有一个起始时间和终止时间。 为了简化计算，这两个时间使用两个整数来表示，取值范围为0到1,000,000,000。 例如，其中一份保单的起始时间t=3且终止时间t=9，那么这份保单的有效区间则覆盖了6个单位时间。 可是，由于个人原因，该客户想退掉其中1份保单，求剩余保单能覆盖的最大单位时间总量是多少？

输入输出格式：

我们会在当前目录给定一个输入文件 “input.txt”

  • 该文件第一行是一个整数N（0<N<=100,000），表示接下来总共有N行。 接下来的N行，每行表示一份保单在0到1,000,000,000范围内的起始以及终止时间（以空格分割）。 所有的终止时间都是不同的。不同的保单能覆盖的时间也可能会重叠。

请给出一个输出文件 “output.txt”

  • 该文件中请输出一个数，表示客户退保1份保单仍能得到覆盖的最大单位时间总量。

输入输出举例：

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

输出文件(output.txt)：
7

题目分析

  • 最多会有10万个区间，循环、排序起来的耗时还在能接受的范围
  • 区间的两个端点数值，符合32位int型范围，不会溢出
  • 题目未涉及到大数的运算，应该主要是考算法实现，只要理解题目，加以适当算法嵌套，解题应该不难。

暴破原理读懂题目：
假设分配10亿个桶，分别对应10亿段小区间（数组可实现），每个保单读入时便在对应桶里加一个球（+1操作），录完之后，再找到最无用的保单剔除，最终根据有多少个桶有球，就是题目的答案。

解题思路

这道题其实是一个动态规划的题，因为每次保单的录入，都会影响最优选择。

最无用的保单怎么找，其实分两种情况：

  • 每个保单都不重叠，直接找跨越区间最短的即可
  • 保单交叉重叠。
    • 这里我选择徒手画多个圆形，任意交叉来帮助理解（因为本题是多个圆形重叠的简化版）。
    • 最终发现，只需要计算出每个圆自己独立拥有的区域大小（本题是区间大小）即可，算出来后再筛选最小值，就得到最无用的保单，剔除即可。

我采用的算法逻辑

  • 1.依次读取N个保单，并计算保存每个保单的区间长度
  • 2.按保单起点、终点递增方式，进行二级快速排序，便于后面做大区段拆分。
  • 3.划分成大区间，每个大区间都不重合（多个重叠的小区间则取最小&最大值作为大区间），这样只要最后进行累加计算即可。
  • 4.重叠的小区间逐个计算权重（独立拥有的区域大小），权重最小的为最无用的保单。
  • 5.权重计算优化，当重叠区域出现权重为0时（类似同心圆情况，即被包含了），直接返回此项为最无用保单，减去此权重就是答案了。
  • 6.本来还想考虑如何省略快排所占用(复杂度NLogN)的时间，想了一些逻辑没有深入，总感觉如果区间段很多的话还是划分大区间会好一点，所以没有再做优化。

代码实现

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

struct node
{
    int start;
    int end;
    int range;
    int weight;
}s[100000];

struct range {
    int min_pos;
    int max_pos;
    struct node data;
};

int cmp (const void * a, const void * b)
{
    struct node* c = (struct node*)a;
    struct node* d = (struct node*)b;
    if(c->start != d->start) {
        return c->start - d->start;
    } else {
        return c->end - d->end;
    }
}

int calWeight(int cur_pos, int start, int end, int length) {
    int overlap_pre=0, overlap_next=0, universe=0;
    int i, j, tmp;

    i = cur_pos-1;
    while(i>=start && s[i].end>s[cur_pos].start) {
        tmp = s[i].end - s[cur_pos].start;
        if(overlap_pre < tmp) {
            overlap_pre = tmp;
        }
        i--;
    }

    j = cur_pos+1;
    while(j<end && s[j].start < s[cur_pos].end) {
        if(s[j].end < s[cur_pos].end) {
            return -1;
        }
        tmp = s[cur_pos].end - s[j].start;
        if(overlap_next < tmp) {
            overlap_next = tmp;
        }
        j++;
    }

    universe = s[cur_pos].range - overlap_pre - overlap_next;

    return (universe<0 ? 0 : universe);
}

struct range distinctRange(int pos, int N) {
    int min_pos, max_pos, i, length, useless_weight=-9999;
    struct range res;
    min_pos = max_pos = pos; i = pos + 1;
    while(i<N && s[i].start < s[max_pos].end) {
        if(s[i].start < s[min_pos].start) {
            min_pos = i;
        }
        if(s[i].end > s[max_pos].end) {
            max_pos = i;
        }
        i++;
    }
    length = s[max_pos].end - s[min_pos].start;
    res.min_pos = pos; res.max_pos = i - 1;
    if(i == pos+1) {
        s[pos].weight = s[pos].range;
        useless_weight = s[pos].weight;
    } else {
        for(int j=pos; j<i; j++) {
            s[j].weight = calWeight(j, pos, i, length);
            if(s[j].weight == -1) {
                res.data.start = s[min_pos].start;
                res.data.end = s[max_pos].end;
                res.data.range = length;
                res.data.weight = 0;
                return res;
            }
            if(useless_weight == -9999 || s[j].weight<useless_weight) {
                useless_weight = s[j].weight;
            }
        }
    }
    
    res.data.start = s[min_pos].start;
    res.data.end = s[max_pos].end;
    res.data.range = length;
    res.data.weight = useless_weight;
    return res;
} 

int main()
{
    int N, i, total=0;
    FILE * fp;
    struct range g_range = {0}, g_min_range={0};
    
    fp = fopen ("input.txt", "r+");
    rewind(fp);
    fscanf(fp, "%d", &N);
    
    for(i=0; i<N; i++) {
        fscanf(fp, "%d %d", &s[i].start, &s[i].end);
        s[i].range = s[i].end - s[i].start;
    }
    
    qsort(s, N, sizeof(s[0]), cmp);

    i=0;
    while(i < N) {
        g_range = distinctRange(i, N);
        i = g_range.max_pos;
        total += g_range.data.range;
        if(g_min_range.max_pos==0 || g_range.data.weight < g_min_range.data.weight) {
            g_min_range = g_range;
        }
        i++;
    }

    total -= g_min_range.data.weight;

    FILE *fpt;
    fpt = fopen("output.txt","w");
    fprintf(fpt,"%d",total);
    fclose(fpt);

    fclose(fp);
    return(0);
}