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

问题描述

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

判断 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; }} }

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

问题解答

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);} }}回答2：

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

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

# -*- 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 Falset1 = '12:30:00-04:20:00't2 = '03:00:00-22:23:00'if is_mixed(t1, t2): print '有交集!'else: print '木有交集!'

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

转换成时间戳能方便比较点回答6：

这样可以从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])回答7：

把时间转换为整型123000, 反向判断a -- bc -- d 这两个时间段，在什么情况下没有交集

b < c

a > d