Submission #109199

---

Source Code Expand

import scala.collection.mutable

object Main {
  def main(args: Array[String]) {
    val n = readInt
    val times: Seq[(Time, Time)] = (1 to n) map { i =>
      val (rawS, rawE) = readf2("{0}-{1}")
      (Time.fromString(rawS.toString), Time.fromString(rawE.toString))
    }
    val periods = times.map(Period.roundTime).sorted(PeriodOrdering)
    val resultStack = periods.foldLeft(mutable.Stack[Period]())(stackFold)
    resultStack.toList.reverse.foreach(println)
  }

  def stackFold(seq: mutable.Stack[Period], p: Period): mutable.Stack[Period] = {
    if(seq.isEmpty) seq.push(p)
    else if(isOverrap(seq.top, p)) {
      val last = seq.pop
      seq.push(join(last, p))
    }
    else seq.push(p)
    seq
  }

  def join(fst: Period, snd: Period): Period = {
    require(fst.start <= snd.start)
    require(fst.end >= snd.start)
    Period(fst.start, TimeOrdering.max(fst.end, snd.end))
  }

  def isOverrap(fst: Period, snd: Period): Boolean = {
    require(fst.start <= snd.start)
    fst.end >= snd.start
  }
}

case class Time(hour: Int, minutes: Int) extends Ordered[Time] {
  override def toString() =
    "%02d".format(hour) + "%02d".format(minutes)
  def compare(that: Time): Int = TimeOrdering.compare(this, that)
}

object Time {
  def fromString(str: String): Time = {
    val hour = str.substring(0, 2).toInt
    val min = str.substring(2, 4).toInt
    Time(hour, min)
  }
}

object TimeOrdering extends Ordering[Time] {
  def compare(a: Time, b: Time) = {
    val hour = a.hour compare b.hour
    if(hour == 0) a.minutes compare b.minutes
    else hour
  }
}

case class Period(start: Time, end: Time) {
  override def toString(): String = Array(start, end).mkString("-")
}

object Period {
  def roundTime(start: Time, end: Time): Period = {
    val roundStart = Time(start.hour, round(start.minutes, false))
    val roundEndMin = round(end.minutes, true)
    val roundEnd = Time(end.hour + roundEndMin / 60, roundEndMin % 60)
    Period(roundStart, roundEnd)
  }
  def roundTime(se: (Time, Time)): Period =
    roundTime(se._1, se._2)

  /**
    * round per 5
    * @param min: integer
    * @param isRev: true -> revaluation, false -> devaluation
    */
  def round(min: Int, isRev: Boolean) = {
    val per5 = min / 5 + (if(min % 5 != 0 && isRev) 1 else 0)
    per5 * 5
  }
}

object PeriodOrdering extends Ordering[Period] {
  def compare(a: Period, b: Period) = {
    val start = a.start compare b.start
    if(start == 0) a.end compare b.end
    else start
  }
}

Submission Info

Judge Result