時間帯重複チェック（応用編）その2
お題：時間帯重複チェック（応用編） - No Programming, No Life をもう一度解く。
フラグ方式には及ばないが計算量を改善した方法に辿り着いた*1。フラグ方式は bucket sort のように限定条件に気づいているので気づいていない方式では太刀打ちできない。
まずは Groovy で
class Time implements Comparable<Time> { int h, m boolean e Time(boolean e, int h, int m) { this.e = e this.h = h this.m = m } int compareTo(Time t) { h <=> t.h ?: m <=> t.m ?: e <=> t.e } List toList() { [h, m] } } def time(int h1, int m1, int h2, int m2) { def t1 = new Time(false, h1, m1) def t2 = new Time(true, h2, m2) assert t1 <= t2 [t1, t2] } def overlaps(input) { def times = input.collect { time(it) }.flatten() def n = 0 // 時間の昇順にソートする (同時刻の場合は開始 < 終了) def results = times.sort().inject([]) { acc, t -> if (!t.e) n++ // 重複している数が 1->2 のときの重複時間開始 // 重複している数が 2->1 のときの重複時間終了 if (n == 2) t.e ? acc << (acc.pop() + t.toList()) : acc << t.toList() if (t.e) n-- acc } println "入力：${input.join(', ').tr('[]','()')}" println "出力：${results.join(', ').tr('[]','()')?:'なし'}" } println "例1)" overlaps([[12, 0, 13, 0], [10, 0, 12, 15]]) println "例2)" overlaps([[16, 0, 23, 0], [9, 0, 17, 0], [5, 0, 10, 30]]) println "例3)" overlaps([[12, 0, 23, 0], [13, 0, 14, 0], [15, 0, 16, 0], [17, 0, 18, 0], [19, 0, 20, 0], [21, 0, 22, 0]]) println "例4)" overlaps([[10, 0, 12, 0], [11, 0, 11, 30], [10, 30, 11, 15]]) println "例5)" overlaps([[9, 0, 17, 0], [19, 0, 21, 0]])
前回書くのをわすれていたが compareTo で ?: 演算子を使うと楽できることに気がついた。
これを見ながら Haskell に翻訳する。
import Data.List overlaps = reverse . snd . foldl selectOverlaps (0, []) . sort . concatMap toTimes where toTimes (h1, m1, h2, m2) | (h1, m1) <= (h2, m2) = [(h1, m1, False), (h2, m2, True)] | otherwise = error "input error" selectOverlaps (1, ts) (h1, m1, False) = (2, (h1, m1, 0, 0):ts) selectOverlaps (2, (h1, m1, _, _):ts) (h2, m2, True) = (1, (h1, m1, h2, m2):ts) selectOverlaps (n, ts) (_, _, False) = (n+1, ts) selectOverlaps (n, ts) (_, _, True) = (n-1, ts) ex1 = [(12, 0, 13, 0), (10, 0, 12, 15)] ex2 = [(16, 0, 23, 0), (9, 0, 17, 0), (5, 0, 10, 30)] ex3 = [(12, 0, 23, 0), (13, 0, 14, 0), (15, 0, 16, 0), (17, 0, 18, 0), (19, 0, 20, 0), (21, 0, 22, 0)] ex4 = [(10, 0, 12, 0), (11, 0, 11, 30), (10, 30, 11, 15)] ex5 = [(9, 0, 17, 0), (19, 0, 21, 0)] main = do putStrLn "ex1)" print $ ex1 print $ overlaps ex1 putStrLn "ex2)" print $ ex2 print $ overlaps ex2 putStrLn "ex3)" print $ ex3 print $ overlaps ex3 putStrLn "ex4)" print $ ex4 print $ overlaps ex4 putStrLn "ex5)" print $ ex5 print $ overlaps ex5
Groovy で変数を使ったのでどうかと思ったが*2さっくり書けた。 昨日の苦労が嘘のようだ。
日本語は化けたので出力をあわせることはあきらめた。
