快速判断&求出区间相交的长度

有两个区间A[a1,b1], B[a2,b2],判断这两个区间有没有交集。我们可以分为两种思维来判断:

 

/**
  *思路就是如果两个区间不相交,那么最大的开始端一定大于最小的结束端
  **/

if(max(a1, a2) < min(b1, b2)){
    return "有交集"
}else{
    return "无交集"
}

 

给你两个区间[a, b]和[c, d],如果让你求出这两个区间的相交长度,你会怎么做呢?
不出意外的话,大多数同学就会进行分类讨论,看看那个区间在前,那个区间在后,分两种情况,然后对区间相交还是覆盖又分了两种情况。

 

int main()
{
    while(~scanf("%d%d%d%d", &a, &b, &c, &d)) {
        int len;
        if(b < c || a > d) len = 0;
        else {
            //先分区间先后,再分区间相交还是覆盖
            //这就是普通做法
            if(c >= a) {
                if(d <= b) len = d-c+1;
                else len = b-c+1;
            }else {
                if(b <= d) len = b-a+1;
                else len = d-a+1;
            }
        }
        printf("%d\n", len);
    }
}

【快速求法】

int main()
{
    while(~scanf("%d%d%d%d", &a, &b, &c, &d)) {
        int len;
        int s = min(b, d) - max(a, c) + 1;
        len = max(0, s);
        printf("%d\n", len);
    }
}

 

全部评论

相关推荐

渴望wlb的牛油果很...:直说卡第一学历不就行了 非得拐弯抹角
点赞 评论 收藏
分享
09-22 09:42
门头沟学院 Java
牛客37185681...:马德,我感觉这是我面过最恶心的公司,一面是两个女hr,说什么实习前几个月属于试用期,试用期过了才能转成正式实习生,我***笑了,问待遇就是不说,问能不能接受全栈,沙币公司
如果可以选,你最想去哪家...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务