route150 さんの「時間帯重複チェック：応用編１」への返信

discrete_time.hs

{-# LANGUAGE ViewPatterns #-}
-- route150 さんの「時間帯重複チェック：応用編１」への返信コード
-- 第４のコーナケースを通るようにしてみた。（時間軸を２倍にしなくてもOKです）
-- 元の答案の出典：http://d.hatena.ne.jp/route150/20110401/1301661345

import Control.Applicative
import Data.List

type Time = (Int, Int)
type TimeSpan = (Int, Int, Int, Int)

-- solve :: [TimeSpan] -> [TimeSpan]
solve :: [TimeSpan] -> [[Time]]
solve = do
  let conv (h1, m1, h2, m2) = [h1 * 60 + m1 .. h2 * 60 + m2 - 1]
      parse xs = case span ((1 <) . snd) <$> span ((<= 1) . snd) xs of
        (_, ([]                                                   , _  )) -> []
        (_, (((,) <$> head <*> (+ 1) . last) . map fst -> (m1, m2), xs')) -> map (`divMod` 60) [m1, m2] : parse xs' 
  parse . map ((,) <$> head <*> length) . group . sort . concatMap conv

main :: IO ()
main = do
  let samples = [
          -- 例1(出力：(12, 0, 12, 15))
          [(12, 0, 13, 0), (10, 0, 12, 15)],
          -- 例2(出力：(9, 0, 10, 30), (16, 0, 17, 0))
          [(16, 0, 23, 0), (9, 0, 17, 0), (5, 0, 10, 30)],
          -- 例3(出力：(13, 0, 14, 0), (15, 0, 16, 0), (17, 0, 18, 0), (19, 0, 20, 0), (21, 0, 22, 0))
          [(12, 0, 23, 0), (13, 0, 14, 0), (15, 0, 16, 0), (17, 0, 18, 0), (19, 0, 20, 0), (21, 0, 22, 0)],
          -- 例4(出力：(10, 30, 11, 30))
          [(10, 0, 12, 0), (11, 0, 11, 30), (10, 30, 11, 15)],
          -- 例5(出力：なし)
          [(9, 0, 17, 0), (19, 0, 21, 0)],
          -- 例x(出力：なし)
          [(9, 0, 19, 0), (17, 0, 21, 0)],
          -- コーナケース1(出力：なし)
          [(1, 0, 2, 0), (2, 0, 3, 0)],
          -- コーナケース2(出力：(1, 59, 2, 0))
          [(1, 0, 2, 0), (1, 59, 3, 0)],
          -- コーナケース3(出力：(0, 0, 0, 1), (23, 59, 24, 0))
          [(0, 0, 24, 0), (0, 0, 0, 1), (23, 59, 24, 0)],
          
          -- コーナケース4 (0, 0, 0, 1), (0, 2, 0, 3)
          [(0, 0, 0, 1), (0, 2, 0, 3), (0, 0, 0, 3)]
        ]
  mapM_ (print . solve) samples

-- 実行環境
-- >ghc --version
-- The Glorious Glasgow Haskell Compilation System, version 6.12.3

-- 出力結果
{-
[[(12,0),(12,15)]]
[[(9,0),(10,30)],[(16,0),(17,0)]]
[[(13,0),(14,0)],[(15,0),(16,0)],[(17,0),(18,0)],[(19,0),(20,0)],[(21,0),(22,0)]]
[[(10,30),(11,30)]]
[]
[[(17,0),(19,0)]]
[]
[[(1,59),(2,0)]]
[[(0,0),(0,1)],[(23,59),(24,0)]]
[[(0,0),(0,1)],[(0,2),(0,3)]]
-}