Re: [問題] 資料的比較、插入、排序

[gene07 (-.-)]

※ 引述《cowbaying (是在靠北喔)》之銘言：
:     schedule.addtask(new Task(2, 20, 'A1'));
:     schedule.addtask(new Task(8, 10, 'A2'));
:     schedule.addtask(new Task(10, 15, 'A3'));
:     schedule.addtask(new Task(12, 10, 'A4'));
:     taskBs.add(new Task(2, 2, 'B1'));     (實際長度8)
:     taskBs.add(new Task(12, 10, 'B2'));   (實際長度26)
:     taskBs.add(new Task(22, 3, 'B3'));    (實際長度29)
:     taskBs.add(new Task(12, 50, 'B4'));   (實際長度66)
: A1          A2        A3           A4
: |>!---------|>>>>-----|>>>>>-------|>>>>>>-----
:   |>-!                                         |>>>>>>-----|>>>>>>>>>>>-|>>~~~
:   B1                                           B2          B3           B4
: 我對這個機制的理解如上圖
: A是主要的
: B能否執行要看A延遲的時間是否足夠把B插入、執行、延遲跟切換回A的時間容納進去
: 原PO的文字描述實在是看不太懂
: 如果B的延遲時間會連帶延遲到A的時間
: 那麼根本不須排序了
: A執行完換B就好



我的意思是...

假設...


(4,10,'A1')   |   (2,2,'B1')
              |
(4,10,'A2')   |   (2,20,'B2')
              |
(2,5,'A3')    |   (2,5,'B3')



  A1                                       A2
  |>!--------------------------------------|>!-------
     (往B,2秒)|>!------------------|>!---------------
              B1 (B1做完delay 2s)  B2 (B往A,2秒)


這樣剛好從A到B來回一次4秒+B1執行的兩秒和delay兩秒+B2的執行2秒

剛好可以插入到A1的delay10秒內...而B2的delay 20秒是從B回到A開始算

所以A2開始執行時B2 delay剩18秒..A2動作做完B2 delay剩14秒

A2 delay 10秒結束B2 delay剩10秒 A3動作做完B2 delay剩2秒

此時A移動到B剛好2秒 可以執行B3

應此就可以成功排序成 A1 B1 B2 A2 A3 B3
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.250.82.82
※ 文章網址: https://www.ptt.cc/bbs/java/M.1473147809.A.FFB.html
推 cowbaying: 我大概了解了  B的延遲可以切割
我完全沒有頭緒...~"~
→ cowbaying: 你等我用FX寫一個有進度表的模擬程式給你看看吧  XD

魯弟我想到了一個方法，不知道這樣行不行....



(4,10,'A1')   |   (2,2,'B1')
              |
(4,10,'A2')   |   (2,20,'B2')
              |
(2,5,'A3')    |   (2,5,'B3')

創一個最後輸出的array

然後把執行動作和delay的時間都拆成1秒1秒去判斷

執行動作假設為1，delay動作為0

A1      (往B移兩秒)         A2      (往B移兩秒)       A3
1,1,1,1,1,1,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,1,1,1,1,0,0,0,0,0
                        (往A移動兩秒)             (往A移動兩秒)
            B1      B2                                          B3
            1,1,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0


然後把A動作跟B動作去做 & 如果不行A就往後一格繼續跟B比較，

全部都等於0代表排序完成



※ 編輯: gene07 (36.230.202.56), 09/09/2016 22:25:29
→ ssccg: 一秒一秒去比是對的，但是不用把輸出轉出來，用範圍去比
→ ssccg: 但是就是我之前說的，如果輸入n個，每個值為k bit，這演算
→ ssccg: 法複雜度是O(n^2 * 2^k)，雖然是對的...
→ ssccg: 其實我一開始想到的作法就是
→ ssccg: AAAAAA********AAAAAA********AAAA***(後面可補*****...
→ ssccg: BBBBBBBB******************BBBB***
→ ssccg: 然後直接用string match的演算法去跑就好了