baidu笔试题 IP段问题

Security公司的网络管理工程师Mr. leak最近发现有不少来自公司外部IP的请求，试图非法访问公司内部资源，为了不影响数据访问流程。
他不得不写一个高效的程序――一个工作在Ipv4上的防火墙，如果请求来自非授权的ip地址，则将请求丢弃。为了便于管理，通过文本文件IP.TXT

162.105.91.163
59.66.105.0  59.66.105.255
211.71.0.0  211.71.255.255
限制：IP段的起止地址间以空格隔开。文件不超过10万行，内存不超过4M字节。
要求：请编写一个程序，读入IP.TXT文件。并从标准输入接受一个IP地址。如果该地址在授权范围内，则在标准输出上打印Y,否则打印N.如果输入为一个空行，程序结束。
 请给出思路（文字描述），完成代码，分析你采用算法的优劣。
 请列举测试方法和思路

发信人: Curvelet (小曲线), 信区: Algorithm
标  题: Re: 谈一条网上的百度笔试题
发信站: 水木社区 (Mon Oct 15 20:59:18 2007), 站内

ip 段是可以合并的，
不需要用 trie 或者 interval tree，
用个数组+二分查找即可。

先把 ip 段改写成 ip 区间形式 [ip_a, ip_b]，
ip_a 是起始 ip 地址， ip_b 是结束 ip 地址。
现对所有 ip 区间按 ip_a 排序，
扫描一遍排序结果，
合并相交的 ip 区间，
结果存在一个数组中。

对于给定的 ip_c，
用二分查找在数组中找到最大的 ip_a <= ip_c，
然后看 ip_c 是否在查找到的区间中即可。

最多 10万行数据，每行对应两个 ip 共 8 字节，
最多 0.8MB。

ps:以ip_a升序排序，顺序扫描ip_b,并记录ip_b的最大值，若当前项的ip_a>以上ip_b 的最大值，则生成一个区间段，以下类似。
------------------------------------------------------------------------------------------------------------------------
2005年百度之星有道求重叠区间大小的题目，和上面的解题思路类似，上面是求并，这里是求交：

题目描述：请编写程序，找出下面"输入数据及格式"中所描述的输入数据文件中最大重叠区间的大小。
对一个正整数n，如果n在数据文件中某行的两个正整数（假设为A和B）之间，即A<=n<=B或A>=n>=B，则n属于
该行；如果n同时属于行i和j，则i和j有重叠区间；重叠区间的大小是同时属于行i和j的整数个数。
例如，行（10 20）和（12 25）的重叠区间为[12 20]，其大小为9；行（20 10）和（12 18）的重叠区间为
[12 18]，其大小为7；行(20 10)和（20 30）的重叠区间大小为1。

输入数据：程序读入已被命名为input.txt的输入数据文本文件，该文件的行数在1到1,000,000之间，每行有
用一个空格分隔的2个正整数，这2个正整数的大小次序随机，每个数都在1和2^32-1之间。（为便于调试，
您可下载测试input.txt文件，实际运行时我们会使用不同内容的输入文件。）

输出数据：在标准输出上打印出输入数据文件中最大重叠区间的大小，如果所有行都没有重叠区间，则输出0。

评分标准：程序输出结果必须正确，内存使用必须不超过256MB，程序的执行时间越快越好。

思路：按起点降序排序，扫描一遍，维护当前线段之前的线段对后面造成的最远阴影

代码如下：
#include <stdio.h>
#include <stdlib.h>

struct node{
     unsigned x;
    unsigned y;
}a[1000000];

int compare(const void *a,const void *b)
{
    struct node *da=(struct node*)a;
    struct node *db=(struct node*)b;
    return (da->x)<(db->x);
  }

int main()
{
    unsigned i,j;
    unsigned n=0;
    freopen("qujian.txt","r",stdin);
   while(scanf("%u%u",&i,&j)!=EOF)
  {
    if(i<j)
    {
        a[n].x=i;
        a[n].y=j;
    }  
    else
    {
        a[n].x=j;  
        a[n].y=i;
    }
    n++;
}
    qsort(a,n,sizeof(struct node),compare);  //以x 降序排序
    unsigned max;                                   
    unsigned tmp;                      
     unsigned ans=0;
     max=a[0].y;
    for(i=1;i<n;i++)
    {
      if(a[i].y>max)
       {
         tmp=max;
         max=a[i].y;
      }
   else
        tmp=a[i].y;
   if((tmp-a[i].x+1)>ans)    //以本节点x为起点对后面造成的最远阴影
       ans=tmp-a[i].x+1;
  }
    printf("%u\n",ans);
   return 0;
}