POJ百练 - 2808:校门外的树

链接：

http://poj.grids.cn/practice/2808

方法1(空间换时间)：

#include <stdio.h>

int main()
{
    int L, M;
    int nTrees[10005] = {0};
    int start, end;
    int nCount = 0;

    scanf("%d%d", &L, &M);
    while (M--)
    {
        scanf("%d%d", &start, &end);
        for (int i = start; i <= end; ++i)
        {
            nTrees[i] = 1;
        }
    }

    for (int i = 0; i <= L; ++i)
    {
        if (nTrees[i] == 0)
        {
            nCount++;
        }
    }

    printf("%d\n", nCount);
    return 0;
}

方法2(合并区间)：
思想是将所有区间存储在数组里面,对所有区间以下限为标准排序,然后从头至尾扫描区间数组,合并区间的方法是：当前区间初始化为第一个区间,然后判断下一个区间的下限是否已经超过当前区间的上限,如果是这样的话,就无法继续合并了,那么就继续已经合并区间的长度,重新开始一次新的合并,否则的话,将下一个区间合并到当前区间起来。。。

#include <stdio.h>
#include <stdlib.h>
#define M_MAX 100 + 2
struct Area
{
    int start;
    int end;
};
int CompareArea(const void *elem1, const void *elem2)
{
    return ((Area*)elem1)->start - ((Area*)elem2)->start;
}
int main()
{
    Area area[M_MAX], temp;
    int L = 0;
    int M = 0;
    int count = 0;
    scanf("%d%d", &L, &M);
    for (int i = 0; i < M; ++i)
    {
        scanf("%d%d", &area[i].start, &area[i].end);
    }
    qsort(area, M, sizeof(Area), CompareArea);

    temp = area[0];
    for (int i = 1; i < M; ++i)
    {
        if (area[i].start <= temp.end)
        {
            if (area[i].end > temp.end)
            {
                temp.end = area[i].end;
            }
        }
        else
        {
            count += temp.end - temp.start + 1;
            temp = area[i];
        }
    }
    count += temp.end - temp.start + 1;

    printf("%d\n", L + 1 - count);

    return 0;
}

整个算法的时间复杂度是 O(M * logM) + O(M)…