作者leslieha (懂的付出才會幸福)
看板Prob_Solve
標題[問題] 時間比較
時間Thu Sep 6 21:51:27 2012
問題
有n個排程
每個排程有 start time(HH:MM:SS) 跟 interval
例如
排程一
start_time = 0:01:30
interval = 00:00:30
那 0:00:00 0:00:30 0:01:00 0:01:30 ... 23:59:30 皆屬於排程一
排程二
start_time = 0:00:10
interval = 3:30:00
那 0:00:10 3:30:10 7:00:10 10:30:10 14:00:10 ... 21:30:10 皆屬於排程二
雖然21:30:10 + 3:30:00 = 25:00:10 % 24:00:00 = 1:00:10
但 超過一天應該算用 0:00:10
要檢查各個排程會不會相衝途
-----------------------------------------------------------
目前想到的解法
一天有 60x60x24 = 86400秒
把排程一想成
start_time = 90
interval = 30
0 30 60 90 ... 86370 皆屬於排程一
A1 A2 A3 A4 An
把排程二想成
start_time = 10
interval = 12600
那 10 12610 25210 ... 77410 皆屬於排程二
B1 B2 B3 Bn
要逐一比較 A1~An B1~Bn有無相等
先找 30 跟 12600的最小公倍數 = 12600
就比較
90+(30x0) ~ 90+(30x420) 是否有跟
10+(12600x0) ~ 10+(12600x1) 相等
---------------------------------------------------------------------
本來有想另一個
開一個大array
可以存86400 bit (2700-btye)
把每一排程所占據的時間設起來 (set to 1)
但這樣無法得知相衝途的排程是那兩個
故只好兩兩作比較
請問
是否有其它解決辦法?
或提供想法
謝謝
--
用程式語言c解
--
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 182.235.124.249
1F：推 flere:如果是我的話我會開一個86400的vector,有排程就開始塞 09/06 22:08
2F：→ flere:最後從0看到86400,底下超過1個的就是有衝突,同時也知道是哪 09/06 22:09
3F：→ flere:幾個是衝突的排程 09/06 22:09
4F：→ flere:有點花記憶體就是了XD 09/06 22:10
5F：→ yauhh:你的問題說"衝突",是指同時只能執行一件行程嗎? 09/06 22:35
6F：→ leslieha:@yauhh 是的 同一秒 只能由一個排程所占據 09/06 22:48
7F：推 DJWS:有數學解法 請查中國餘數定理 09/07 05:57
※ leslieha:轉錄至看板 Programming 09/07 14:18