javascript - 求时间段之间的交集的最优解-PHP中文网问答

文章专题 AI工具学习下载问答源码最近更新

PHP

会员中心讲师中心微信公众号

javascript - 求时间段之间的交集的最优解

PHP中文网 2017-06-30 09:53:32

[Python讨论组]

1429

判断一段时间与一堆一段时间之间是否有交集。有与起止时间相同的判断为有交集
如

判断 
12:30:00--14:20:00
与下列时间段是否有交集
10:00:00-12:00:00,  12:10:00-12:50:00 , 14:30:00-15:00:00

转换为时间戳然后一一循环比较

function is_cross($st1, $et1, $st2, $et2)
    {
        $status = $st2 - $st1;
        if ($status > 0) {
            $status2 = $st2 - $et1;
            if ($status2 >= 0) {
                return false;
            } else {
                return true;
            }
        } else {
            $status2 = $et2 - $st1;
            if ($status2 > 0) {
                return true;
            } else {
                return false;
            }
        }
    }

这能解决问题，但是求更优的方法，最小的时间复杂度

PHP中文网

认证0级讲师

全部回复(7)

世界只因有你2017-06-30 09:55:32 7楼

public function inter(){

    $tar=[6,4];
    if($tar[0]>$tar[1]){
        $temp=$tar[0];
        $tar[0]=$tar[1];
        $tar[1]=$temp;
    }
    $all=[
        [5,6],
        [7,9],
        [1,4],
        [3,1],
        [1,3],
        [8,7]
    ];
    //排序
    foreach ($all as &$v){
        if($v[0]>$v[1]){
            $temp=$v[0];
            $v[0]=$v[1];
            $v[1]=$temp;
        }
    }
    foreach ($all as $k=>$v){
        $left=$tar[0]>$v[1];
        $right=$v[0]>$tar[1];
        if(!($left||$right)){
            var_dump($v);
        }
    }

}

赞 +0

添加回复

大家讲道理2017-06-30 09:55:32 6楼

将时间转化为时间戳，然后-------对比。

赞 +0

添加回复

我想大声告诉你2017-06-30 09:55:32 5楼

如果这个 一堆一段时间 需要被多次使用: 可以用线段树。一次使用时"一一对比"也不会更慢。

赞 +0

添加回复

迷茫2017-06-30 09:55:32 4楼

# -*- coding: utf-8 -*-

def is_mixed(t1, t2):
    '''
    假定时间段格式是："10:00:00-12:00:00"
    判断 t1，t2是否有交集
    '''
    s1, e1 = t1.split("-")
    s2, e2 = t2.split("-")

    if s1 > e2 and s2 > e1:
        return True
    if s2 > e1 and s1 > e2:
        return True

    return False

t1 = "12:30:00-04:20:00"
t2 = "03:00:00-22:23:00"

if is_mixed(t1, t2):
    print "有交集!"
else:
    print "木有交集!"

python版本，js应该也是一样的

赞 +0

添加回复

ringa_lee2017-06-30 09:55:32 3楼

转换成时间戳能方便比较点

赞 +0

添加回复

怪我咯2017-06-30 09:55:32 2楼

这样可以从periods挑出和period有交集的时间段。

period  = "12:30:00-14:20:00"
periods  = ["10:00:00-12:00:00", "12:10:00-12:50:00","14:30:00-15:00:00"]

print([x+'-'+y for [b,e] in [period.split("-")] for [x,y] in [p.split("-") for p in periods] if x<=e and y>=b])

赞 +0

添加回复