Created
April 3, 2011 08:42
-
-
Save akihiro4chawon/900303 to your computer and use it in GitHub Desktop.
答案:時間帯重複チェック(応用編) - 一番良いアルゴリズムを頼む
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// お題:時間帯重複チェック(応用編) | |
// <http://d.hatena.ne.jp/fumokmm/20110329/1301403400> | |
// に対する、最良のアルゴリズムを考えた。 by @akihiro4chawon | |
/** 時刻; Time Point */ | |
case class Point(hour: Int, minutes: Int) extends Ordered[Point] { | |
def inMinutes = 60 * hour + minutes | |
override def compare(that: Point) = | |
this.inMinutes compare that.inMinutes | |
} | |
object Point { | |
implicit def mkOrderingOps(p: Point) = implicitly[Ordering[Point]].mkOrderingOps(p) | |
} | |
/** 時間帯; Time Interval */ | |
case class Interval(val beg: Point, val end: Point) extends Ordered[Interval] { | |
override def compare(that: Interval) = | |
(2 * (beg compare that.beg) + (end compare that.end)).signum | |
def and(that: Interval): Option[Interval] = | |
Some(Interval(beg max that.beg, end min that.end)) filter {i => i.beg < i.end} | |
} | |
object Interval { | |
def fromHoursMinutes(h1: Int, m1: Int, h2: Int, m2: Int) = | |
Interval(Point(h1, m1), Point(h2, m2)) | |
} | |
object Test extends Application { | |
type IntTuple4 = (Int, Int, Int, Int) | |
def solve(ts: IntTuple4*) = { | |
def overlaps(ts: List[Interval]): List[Interval] = ts match { | |
case x1 :: x2 :: xs => x1 and x2 match { | |
case Some(lap) => lap :: overlaps(Interval(lap.end, x1.end max x2.end) :: xs) | |
case None => overlaps(x2 :: xs) | |
} | |
case _ => Nil | |
} | |
def merge(ts: List[Interval]): List[Interval] = ts match { | |
case x1 :: x2 :: xs if (x1.end >= x2.beg) => merge(Interval(x1.beg, x2.end) :: xs) | |
case x1 :: xs => x1 :: merge(xs) | |
case Nil => Nil | |
} | |
// ここで、sorted にかかる計算量が O(NlogN) になる | |
// merge(overlaps(ts.toList map (Interval.fromHoursMinutes _).tupled sorted)) | |
// 時刻の離散性に注目し、 bucket sort を使えばO(N)の計算量になる | |
def bucketSort(ts: List[Interval]) = { | |
val bucket = Array.fill(24 * 60)(List[Interval]()) | |
ts foreach {i => bucket(i.beg.inMinutes) ::= i} | |
bucket.toList.flatten | |
} | |
merge(overlaps(bucketSort(ts.toList map (Interval.fromHoursMinutes _).tupled))) | |
} | |
for {arg <-Seq( | |
// 例1(出力:(12, 0, 12, 15)) | |
Seq((12, 0, 13, 0), (10, 0, 12, 15)), | |
// 例2(出力:(9, 0, 10, 30), (16, 0, 17, 0)) | |
Seq((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)) | |
Seq((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)) | |
Seq((10, 0, 12, 0), (11, 0, 11, 30), (10, 30, 11, 15)), | |
// 例5(なし) | |
Seq((9, 0, 17, 0), (19, 0, 21, 0)), | |
)} println(solve(arg :_*) mkString ",") | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
36~39行目は、普段はこんな感じで書いていますw
case x1 :: x2 :: xs =>
x1 and x2 flatmap {i => i :: overlaps(Interval(i.end, x1.end max x2.end) :: xs)} getOrElse overlaps(x2 :: xs)