poj 1089 Intervals

poj 1089 Intervals

#include <iostream>#include <stdio.h>#include <stdlib.h>using namespace std;const int N_MAX = 50000;typedef struct INTERVAL{     int s, e;}INTERVAL_S;INTERVAL_S g_aIntervals[N_MAX]; // 读入区间数// 区间数比较函数int interval_cmp(const void *pOP1, const void *pOP2){    INTERVAL_S *pInterval1, *pInterval2;    pInterval1 = (INTERVAL_S *)pOP1;    pInterval2 = (INTERVAL_S *)pOP2;    if (pInterval1->s < pInterval2->s)  return -1;    if (pInterval1->s == pInterval2->s) return  0;    if (pInterval1->s > pInterval2->s)  return  1;}int main(){    int n;    scanf("%d", &n);    for (int i=0; i<n; i++)    {        scanf("%d %d", &g_aIntervals[i].s, &g_aIntervals[i].e);    }    // 以起点从小到大排序    qsort(g_aIntervals, n, sizeof(g_aIntervals[0]), interval_cmp);    INTERVAL_S cur_interval; // 当前处理区间    // 从前向后线性扫描    int i = 0;    while (i<n)    {        cur_interval = g_aIntervals[i];        // 一个区间的处理        int j = i+1;        while (j<n && g_aIntervals[j].s<=cur_interval.e)        { if (g_aIntervals[j].e > cur_interval.e)     cur_interval.e = g_aIntervals[j].e; ++j;        }        // 打印之        printf("%d %dn", cur_interval.s, cur_interval.e);        i = j;    }    return 0;}