精华内容
下载资源
问答
  • python求解重叠区域线段覆盖总长度

    千次阅读 2017-07-31 21:42:09
    来源于网上的一道面试题目,看到后感觉挺新颖的,正好这一篇博客也有了实现,感觉思路很妙,作者给出来的是Java版本的,这里我简单给出来一下python版本的,先贴一下...依据线段的区间将线段的区间像素单位化,即将计

        来源于网上的一道面试题目,看到后感觉挺新颖的,正好这一篇博客也有了实现,感觉思路很妙,作者给出来的是Java版本的,这里我简单给出来一下python版本的,先贴一下问题的描述:

    问题描述:

    现有一直线,从原点到无穷大。

    这条直线上有N个线段。线段可能相交。

    问,N个线段总共覆盖了多长?(重复覆盖的地区只计算一次)

    思路:

    依据线段的区间将线段的区间像素单位化,即将计算区域的长度转化为所有在覆盖区域中的单位长度的累加即可

    下面是具体的实现:

    #!usr/bin/env python
    #encoding:utf-8
    
    '''
    __Author__:沂水寒城
    功能:求解线段覆盖总长度
    '''
    
    def test_func(num_list):
        '''
        输入:线段起点、终点
        输出:总的覆盖长度
        '''
        start=1000
        end=0
        for one_list in num_list:
            if one_list[0]<start:
                start=one_list[0]
            if one_list[1]>end:
                end=one_list[1]
        #print start, end
        flag=['false']*end
        for i in range(len(num_list)):
            for j in range(num_list[i][0], num_list[i][1]):
                flag[j]=True
        #print flag
        return flag.count(True)
    
    
    if __name__ == '__main__':
        num_list1=[[1,3],[2,7],[9,11],[13,20],[15,30]]
        num_list2=[[1,3],[2,6],[11,12],[10,13]]
        print 'Total Length is:', test_func(num_list1)
        print 'Total Length is:', test_func(num_list2)


    结果如下:


    Total Length is: 25
    Total Length is: 8
    [Finished in 0.7s]


    展开全文
  • 线段重叠

    2018-07-30 20:43:43
    线段重叠是这样来算的,[10 20]和[12 25]的重叠部分为[12 20]。 给出N条线段的起点和终点,从中选出2条线段,这两条线段重叠部分是最长的。输出这个最长的距离。如果没有重叠,输出0。 输入 第1行:线段的...

    X轴上有N条线段,每条线段包括1个起点和终点。线段的重叠是这样来算的,[10 20]和[12 25]的重叠部分为[12 20]。

    给出N条线段的起点和终点,从中选出2条线段,这两条线段的重叠部分是最长的。输出这个最长的距离。如果没有重叠,输出0。

    输入

    第1行:线段的数量N(2 <= N <= 50000)。 
    第2 - N + 1行:每行2个数,线段的起点和终点。(0 <= s , e <= 10^9)

    输出

    输出最长重复区间的长度。

    样例输入

    5
    1 5
    2 4
    2 8
    3 7
    7 9

    样例输出

    4

     

    这个代码我个人觉得已经很简洁了

    #include<iostream>
    #include<algorithm>
    using namespace std;
    struct k
    {
        int s,e;
    }a[50005];
    int cmp(k x,k y)
    {
        if(x.s==y.s)
        return x.e>y.e;
        else
        return x.s<y.s;             左端从小到大,左端相等时右端点从大到小
    }
    int main()
    {
        int n,i,j;
        while(cin>>n)
        {
            int ans=0;
            for(i=0;i<n;i++)
            cin>>a[i].s>>a[i].e;
            sort(a,a+n,cmp);
            for(i=1;i<n;i++)
            {
                if(a[i].e>=a[i-1].e)                                        如果第二个线段的右端点大于他前边的,则挑出前者的右端点减去后者的左端点。
                {
                    ans=max(ans,a[i-1].e-a[i].s);
                }
                else
                {                                                                 若不大于,则用后者的右端点减去左端点,与ans比较
                    ans=max(ans,a[i].e-a[i].s);
                    a[i]=a[i-1];                                          这个很重要,将较长的线段后移,只有这样,才不会漏掉最大线段差产生于不相临的线段中。
                }
            }
            cout<<ans<<endl;
        } 
        return 0;
    }

     

    展开全文
  • 51nod线段重叠

    2018-07-21 11:25:42
    1091 线段重叠  基准时间限制:1 秒 空间限制:131072 KB 分值: 5 难度:1级算法题  收藏  关注 X轴上有N条线段,每条线段包括1个起点和终点。线段重叠是这样来算的,[10 20]和[12 25]的重叠部分为...

    1091 线段的重叠 

    基准时间限制:1 秒 空间限制:131072 KB 分值: 5 难度:1级算法题

     收藏

     关注

    X轴上有N条线段,每条线段包括1个起点和终点。线段的重叠是这样来算的,[10 20]和[12 25]的重叠部分为[12 20]。

    给出N条线段的起点和终点,从中选出2条线段,这两条线段的重叠部分是最长的。输出这个最长的距离。如果没有重叠,输出0。

    Input

    第1行:线段的数量N(2 <= N <= 50000)。
    第2 - N + 1行:每行2个数,线段的起点和终点。(0 <= s , e <= 10^9)

    Output

    输出最长重复区间的长度。

    Input示例

    5
    1 5
    2 4
    2 8
    3 7
    7 9

    Output示例

    4

    贪心:先按结束时间排序之后,依次遍历一遍找到最长的重叠部分。每次找到只比最大的右端点小的值减去左端点。

    #include<map>
    #include<stack>
    #include<queue>
    #include<math.h>
    #include<vector>
    #include<string>
    #include<stdio.h>
    #include<iostream>
    #include<string.h>
    #include<algorithm>
    #define maxn 50005
    #define inf 0x3f3f3f3f3f
    #define ll  long long
    #define mod 10
    #define mem(a,b) memset(a,b,sizeof(a))
    using namespace std;
    struct node{
        int x,y;
    }d[maxn];
    bool cmp(node m,node n){
        if(m.x==n.x)return m.y<n.y;
        return m.x<n.x;
    }
    int main(){
        int n;
        while(~scanf("%d",&n)){
        mem(d,0);
         ll a,b;
         for(int i=0;i<n;i++){
            scanf("%lld%lld",&d[i].x,&d[i].y);
         }
         sort(d,d+n,cmp);
         ll ans=0,maxx=d[0].y,minn=d[0].x;
         for(int i=1;i<n;i++){
            if(d[i].y>maxx){minn=maxx;maxx=d[i].y;}
            else if(d[i].y>minn)minn=d[i].y;
            ans=max(ans,minn-d[i].x);
            }
            printf("%lld\n",ans);
        }
    }
    

     

    展开全文
  • 1091 线段重叠 基准时间限制:1 秒 空间限制:131072 KB 分值: 5 难度:1级算法题 收藏 关注 X轴上有N条线段,每条线段包括1个起点和终点。线段重叠是这样来算的,[10 20]和[12 25]的...

    1091 线段的重叠
    基准时间限制:1 秒 空间限制:131072 KB 分值: 5 难度:1级算法题
    收藏
    关注
    X轴上有N条线段,每条线段包括1个起点和终点。线段的重叠是这样来算的,[10 20]和[12 25]的重叠部分为[12 20]。
    给出N条线段的起点和终点,从中选出2条线段,这两条线段的重叠部分是最长的。输出这个最长的距离。如果没有重叠,输出0。
    Input
    第1行:线段的数量N(2 <= N <= 50000)。
    第2 - N + 1行:每行2个数,线段的起点和终点。(0 <= s , e <= 10^9)
    Output
    输出最长重复区间的长度。
    Input示例
    5
    1 5
    2 4
    2 8
    3 7
    7 9
    Output示例
    4
    

    思路: 对左端点升序排序,右端点降序排序,每次更新右边的最远距离,并拿最远距离和当前最右比较,两者中最小的减去当前左端点的距离与maxn比较,更新最远距离和maxn即可

    Code:

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    const int AX = 5e4+666;
    
    struct Node
    {
    	int l , r;
    }e[AX];
    bool cmp( const Node &a , const Node &b){
    	if( a.l == b.l ) return a.r > b.r;
    	else return a.l < b.l;
    }
    
    int main(){
    
    	ios_base::sync_with_stdio(false);
    	cin.tie(0);
    	int n;
    	cin>>n;
    	for( int i = 0 ; i < n ; i++ ){
    		cin >> e[i].l >> e[i].r;
    	}
    	sort( e, e + n, cmp );
    	int far_r = e[0].r;
    	int maxn = 0;
    	for( int i = 1 ; i  < n ; i++ ){
    		maxn = max( maxn , min(e[i].r , far_r) - e[i].l );
    		if( e[i].r > far_r ){
    			far_r = e[i].r;
    		}
    	}
    	cout<<maxn<<endl;
    	return 0;
    }

    1133 不重叠的线段

    基准时间限制:1 秒 空间限制:131072 KB 分值: 10 难度:2级算法题
    收藏
    关注
    X轴上有N条线段,每条线段有1个起点S和终点E。最多能够选出多少条互不重叠的线段。(注:起点或终点重叠,不算重叠)。
    例如:[1 5][2 3][3 6],可以选[2 3][3 6],这2条线段互不重叠。
    Input
    第1行:1个数N,线段的数量(2 <= N <= 10000)
    第2 - N + 1行:每行2个数,线段的起点和终点(-10^9 <= S,E <= 10^9)
    Output
    输出最多可以选择的线段数量。
    Input示例
    3
    1 5
    2 3
    3 6
    Output示例
    2

    这个和上面的是一种类型,上边求重叠长度,这个求不重叠数量,相对难一点点。 不过差不多。

    思路:还是对左右排序,这次是对右端点升序排序,左端点降序,每次更新右端点。因为是要求不重叠,肯定要覆盖范围小才好。

    #include <iostream>
    #include <algorithm>
    using namespace std;
    const int AX = 1e4+666;
    
    struct  Node
    {
    	int l , r ;
    }e[AX];
    
    bool cmp( const Node &a , const Node &b ){
    	if( a.r == b.r ) return a.l > b.l;
    	else return a.r < b.r;
    }
    
    int main(){
    
    	ios_base::sync_with_stdio(false);
    	cin.tie(0);
    	int n;
    	cin>>n;
    	for( int i = 0 ; i < n ; i++ ) {
    		cin >> e[i].l >> e[i].r;
    	}
    	sort( e , e + n ,cmp );
    	int far_r = e[0].r;
    	int res = 1;
    	for( int i = 1 ; i < n ; i++ ){
    		if( e[i].l >= far_r  ) {
    			res++;
    			far_r = e[i].r;
    		}
    	}	
    	cout<<res<<endl;
    	return 0;
    }


    展开全文
  • 给出N条线段的起点(整数)和终点(整数),从中选择两条线段,使这两条线段重叠部分是最长的。输出这个最长的距离。如果没有重叠,输出0。 Input 多组输入数据,每组测试数据包含两行: 第1行...
  • 51nod1091线段重叠 贪心

    2018-08-02 22:23:51
    线段重叠是这样来算的,10201020和12251225的重叠部分为12201220。 给出N条线段的起点和终点,从中选出2条线段,这两条线段重叠部分是最长的。输出这个最长的距离。如果没有重叠,输出0。 Input 第1行:线段...
  • 线段重叠是这样来算的,1020和1225的重叠部分为1220。 给出N条线段的起点和终点,从中选出2条线段,这两条线段重叠部分是最长的。输出这个最长的距离。如果没有重叠,输出0。 Input: 第1行:线段的数量N(2...
  • 线段重叠是这样来算的,[10 20]和[12 25]的重叠部分为[12 20]。 给出N条线段的起点和终点,从中选出2条线段,这两条线段重叠部分是最长的。输出这个最长的距离。如果没有重叠,输出0。 Input 第1行:线段的...
  • 线段重叠是这样来算的,[10 20]和[12 25]的重叠部分为[12 20]。 给出N条线段的起点和终点,从中选出2条线段,这两条线段重叠部分是最长的。输出这个最长的距离。如果没有重叠,输出0。 Input 第1行:线段的...
  • 线段重叠

    2019-06-20 23:21:53
    线段重叠 1 秒 131,072 KB 5 分 1 级题 //X轴上有N条线段,每条线段包括1个起点和终点。线段重叠是这样来算的,[10 20]和[12 25]的重叠部分为[12 20]。 给出N条线段的起点和终点,从中选出2条线段,这两条...
  • 线段重叠 AC于2018.7.21

    2018-07-30 23:47:32
    线段重叠是这样来算的,[10 20]和[12 25]的重叠部分为[12 20]。 给出N条线段的起点和终点,从中选出2条线段,这两条线段重叠部分是最长的。输出这个最长的距离。如果没有重叠,输出0。 输入输出格式 输入格式...
  • 线段重叠(活动安排)问题 贪心

    千次阅读 2017-04-02 00:36:43
    三个题目都是类似的题目,但是前面两个是对第一个数进行排序,第三题是对第二个数进行排序 第二题:稍微注意一下...1091 线段重叠 基准时间限制:1 秒 空间限制:131072 KB 分值: 5 收藏 关注
  • 线段重叠(贪心)

    千次阅读 2018-08-23 20:47:06
    线段重叠(贪心) 描述 X轴上有N条线段,每条线段包括1个起点和终点。线段重叠是这样来算的,[10 20]和[12 25]的重叠部分为[12 20]。 给出N条线段的起点和终点,从中选出2条线段,这两条线段重叠部分是最长的...
  • 1091 线段重叠

    2018-01-02 17:38:23
    1091 线段重叠 基准时间限制:1 秒 空间限制:131072 KB 分值: 5 难度:1级算法题 收藏 关注 X轴上有N条线段,每条线段包括1个起点和终点。线段重叠是这样来算的,[10 20]和[12 25]的重叠部分为[12 20]。 给...
  • 51nod 1091 线段重叠

    2018-04-26 22:32:11
    1091 线段重叠 基准时间限制:1 秒 空间限制:131072 KB 分值: 5 难度:1级算法题 收藏 关注X轴上有N条线段,每条线段包括1个起点和终点。线段重叠是这样来算的,[10 20]和[12 25]的重叠部分为[12 20]。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,251
精华内容 2,500
关键字:

线段重叠总长度