一道阿里面试题-白红宇

一道阿里面试题

阅读量：4676 次

发布时间：2019-06-09

本文共 1365 字，大约阅读时间需要 4 分钟。

有1，2，3....n个数组，每个数组包含一系列一维线段的表示，每个数组的元素结构为（point，length）（point>=0 且 length>=1，都为整数），表示从point开始长为length的线段，现将n个数组中的线段合并，其中需要考虑数组的优先级：1>2>....>n，高优先级的数组的线段将覆盖并切分重叠的低优先级数组线段。求合并后的数组？

示例：

1数组：（0，2），（6，9）

2数组：（1，3），（7，10）

合并后：（0，2），（2，2），（6，9），（15，2）

输入：

n（数组个数）

依次输入n个数组。

输出：

合并后的数组。

我的想法其实很简单，从第n个数组，往前。一段一段合并。合并过程是：在给定区间中遍历，遇到已经存在的区间边界，进行切分或者覆盖。这个方法的缺点是如果区间很大比如1，100000 就需要循环10万次。所以我做了离散化。这样就ok了。

之前尝试用过set来解决，发现并不可以。

////  main.cpp//  test2////  Created by 小康 on 28/03/2018.//  Copyright © 2018 小康. All rights reserved.//#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             using namespace std;struct Node{ int point; int length; int end; bool operator <(const Node &r) const { if(point == r.point) return end
             
              point=point; this->end=end; this->length = end-point+1; }}a[105][105],res[1005];set
              
                ans;bool sort(Node a,Node b){ if(a.point==b.point) return a.end
               
                 m;int c[10005];int main(){ printf("请输入数组的个数\n"); scanf("%d",&n); int p=1; for(int i=0;i
                
                 =0;i--) { for(int j=0;j
                 
                  r) { tagl[r]=tagl[k]; tagr[tagl[k]]=r; tagl[k]=0; } else { tagr[tagl[k]]=0; tagl[k]=0; } } if(tagr[k]!=0) { if(tagr[k]

我的博客即将搬运同步至腾讯云+社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=1mixekxljlo4b

转载于:https://www.cnblogs.com/dacc123/p/8707670.html

你可能感兴趣的文章