scala 检查列表中是否有重叠时间

rjee0c15  于 2023-10-18  发布在  Scala
关注(0)|答案(3)|浏览(110)

我有一个开放时间的清单,每天这是类型

Map[String, List[(String, String)]]

Key是星期几,列表元素包含Open_from和open_to。下面是示例

Map(MONDAY -> List( (08:00:00, 12:00:00), (13:00:00, 16:00:00)), 
    TUESDAY -> List( (09:00:00, 12:00:00), (13:00:00, 16:00:00)),
  ...
  ...
)

我必须检查以下条件,以检查是否有重叠的时间

  1. Open_to应大于Open_from
    1.如果一天内list中有超过1个元素(如上面的例子),那么第一个元素的open_to应该小于下一个元素的open_from。
    如果Map中有任何重叠的时间,则必须返回true或false。我试着用foldLeft来做,并与列表中的下一个元素进行比较。但是不确定如何返回布尔值。
    你能告诉我怎么做吗?谢谢
    谢谢
kzmpq1sx

kzmpq1sx1#

我认为你走的是正确的路。我在实现中使用了Int而不是times。在可读性方面还有很大的改进空间:

val openingTimes = Map(
    "MONDAY" -> List( (1, 2), (3, 4)), 
    "TUESDAY" -> List( (1, 3), (2, 4))
)

openingTimes.forall { case (_, timeRanges) =>
  timeRanges.forall { case (from, to) => from < to } &&
    timeRanges.foldLeft(true -> Int.MinValue) { case ((nonOverlapping, prevTime), (time)) =>
      (nonOverlapping && prevTime < time._1) -> time._2
    }._1
}
dy2hfwbg

dy2hfwbg2#

你不需要foldLeft。类似这样的东西应该可以检查这两个条件:

val isValid = ranges
  .iterator
  .flatMap { case (a,b) => Seq(a, b) }
  .sliding(2)
  .forall { case Seq(a,b) => a < b }
ukdjmx9f

ukdjmx9f3#

这是我的解决方案,我认为其他解决方案缺少的一个重要部分是假设时间块是有序的,这可能不是这样:

val validSchedule = Map("MONDAY" -> List((8, 12), (13, 16)), 
    "TUESDAY" -> List( (9, 12), (13, 16)),
)
val validUnorderedSchedule = Map("MONDAY" -> List((8, 12), (13, 16)), 
    "TUESDAY" -> List( (9, 12), (13, 16)),
    "WEDNESDAY" -> List((9, 12), (14, 15), (6, 7)), // (6,7) comes after (14,15), but is still valid
)
val invalidSchedule = Map("MONDAY" -> List((8, 12), (13, 16)), 
    "TUESDAY" -> List( (9, 12), (11, 16)),
)
val invalidUnorderedSchedule = Map("MONDAY" -> List((8, 12), (13, 16)), 
    "TUESDAY" -> List((9, 12), (11, 16)),
    "WEDNESDAY" -> List((9, 12), (14, 15), (7, 10)), // (7,10) overlaps with (9,12)
)

def validateSingleTimeBlock(timeBlock: (Int, Int)): Boolean = timeBlock._1 <= timeBlock._2
def validateConsecutiveTimeBlocks(first: (Int, Int), second: (Int, Int)): Boolean = first._2 <= second._1
def combineValidatedTimeBlocks(first: (Int, Int), second: (Int, Int)): (Int, Int) = (first._1, second._2)

def validateSchedule(schedule: Map[String, List[(Int, Int)]]): Boolean = {
  schedule.values
    .map { timeBlocksForDay => timeBlocksForDay.sortBy { _(0) } }  // for each day, order time blocks by opening time
    .forall { timeBlocksForDay =>
        timeBlocksForDay.foldLeft(true -> (Option.empty[(Int, Int)])) { // for each day, we'll reduce the list of time blocks to a pair that represents if the day so far is valid, and if so, what hours have been covered already
          case ((validSoFar, timesAlreadyScheduled), nextTimeBlock) if validSoFar =>
            val validatedTimeBlock = Some(nextTimeBlock) filter (validateSingleTimeBlock)
            val next = (timesAlreadyScheduled, validatedTimeBlock) match {
              case (Some(prev), n) =>
                n filter (validateConsecutiveTimeBlocks(prev, _)) map (combineValidatedTimeBlocks(prev, _)) 
              case (None, n) => n // the first time block we've seen for the day
            }
            (next.isDefined, next)
          case _ => (false, None)
        }._1
    }
}

println(validateSchedule(validSchedule)) // true
println(validateSchedule(invalidSchedule)) // false
println(validateSchedule(validUnorderedSchedule)) // true
println(validateSchedule(invalidUnorderedSchedule)) // false

下面是一个可运行的scastie:https://scastie.scala-lang.org/Gmia1WsnSqGbbZgTJKWoYw

相关问题