javascript - 求時間段之間的交集的最優解

Question

判斷一段時間與一堆一段時間之間是否有交集。有與起止時間相同的判斷為有交集如 {代碼...} 轉換為時間戳然後一一循環比較 {代碼...} 這能解決問題，但是求更優的方法，最小的時間複雜度

世界只因有你 · Answer

公用函數 inter(){

雷雷

大家讲道理 · Answer

將時間轉換為時間戳，然後-------對比。

我想大声告诉你 · Answer

如果這個 一堆一段時間 需要被多次使用: 可以用線段樹。一次使用時"一一對比"也不會更慢。

迷茫 · Answer

# -*- 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應該也是一樣的

ringa_lee · Answer

怪我咯 · Answer

這樣可以從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])

漂亮男人 · Answer

把時間轉換為整數123000, 反向判斷
a -- b
c -- d
這兩個時間段，在什麼情況下沒有交集

b
a > d