非相交范围间的时间范围
我有以下时间表：
7 a.m --------------------- 12 a.m. 2 am .................. 10 a.m
10-------11 3------5
closed closedthe output should be the non-intersecting time ranges:
7-10 a.m, 11 -12 a.m, 2-3 p.m, 5-10 p.m我尝试了减法和减法，但是失败了--一个棘手的部分可能是下面的情况
7 a.m --------------------- 12 a.m. 2 am .................. 10 a.m
10----------------------------------------5
closedthe output should be the non-intersecting time ranges:
7-10 a.m, 5-10 p.m对kotlin的实现有什么想法吗？
我试着对恒河进行减法，但没有奏效
回答 2
Stack Overflow用户
发布于 2022-12-03 21:26:55
下面是一种简单的方法，可以找到不相交的时间范围：
创建一个所有时间范围的列表(例如，在第一个示例中，列表将在上午7点至12点，上午2点至10点)。按照每个范围的开始时间对列表进行排序(在第一个示例中，列表将是上午7点至12点，上午2点至10点)。循环遍历范围列表，并将每个范围与下一个范围进行比较，以查看它们是否相交。如果是这样的话，将这两个区域合并成一个范围。
在第一个例子中，第一个范围(上午7点至12时)将与第二个范围(凌晨2至10时)进行比较，由于它们相交，它们将合并为一个范围(上午7时至10时)。
继续循环遍历列表和合并范围，直到找不到更多的相交范围。在第一个例子中，合并前两个范围后，产生的列表将是上午7点至10点、上午11点至12点、下午2点至5点。
抽样实施情况：
fun findNonIntersectingRanges(ranges: List<Pair<Int, Int>>): List<Pair<Int, Int>> {
// Create a list of ranges
var nonIntersectingRanges = ranges.toMutableList()
// Sort the list by the start time of each range
nonIntersectingRanges.sortBy { it.first }
// Loop through the list of ranges and compare each range with the next range to see if they intersect
for (i in 0 until nonIntersectingRanges.size - 1) {
val currentRange = nonIntersectingRanges[i]
val nextRange = nonIntersectingRanges[i + 1]
// If the current range and the next range intersect, merge them into one range
if (currentRange.second >= nextRange.first) {
val mergedRange = currentRange.first to nextRange.second
nonIntersectingRanges[i] = mergedRange
nonIntersectingRanges.removeAt(i + 1)
}
}
return nonIntersectingRanges
}就这样叫它：
val ranges = listOf(7 to 12, 2 to 10)
val nonIntersectingRanges = findNonIntersectingRanges(ranges)在第一个例子中，产生的非相交范围的列表将是上午7点至10点、上午11点至12点、下午2点至5点。在第二个例子中，结果列表是上午7点到10点，下午5点到10点。
Stack Overflow用户
发布于 2022-12-03 22:28:30
听起来很普通，我怀疑有一些现有的算法，但什么都没有从我的头脑中出来。
我的想法是首先将两个范围列表转换为一个按时间顺序打开/关闭“事件”的单一列表。一个开放范围的开始增加了+1的“开放度”，而它的结束降低了它(-1)。关闭范围的开始也会降低“开放度”，而其结束则会增加“开放度”。然后我们按时间顺序迭代事件，保持当前“开放”级别的信息。每当“开放”级别为1时，这意味着我们处于开场区间的中间，而不是在闭幕式范围内，因此我们完全开放。
假设两个范围的列表最初都是正确排序的，就像在您的示例中一样，我认为它应该可以在线性时间内完成，即使没有这个中间事件列表。然而，这样的实现对于涵盖所有可能的状态来说都是相当复杂的，所以我决定使用一个更简单的解决方案，即我相信O(n * log(n))。此外，这一实现要求开始范围不相互重叠，对于结束范围也是如此：
fun main() {
// your first example
println(listOf(Range(7, 12), Range(14, 22)) - listOf(Range(10, 11), Range(15, 17)))
// second example
println(listOf(Range(7, 12), Range(14, 22)) - listOf(Range(10, 17)))
// two close rangs "touch" each other
println(listOf(Range(8, 16)) - listOf(Range(10, 11), Range(11, 13)))
// both open and close range starts at the same time
println(listOf(Range(8, 16)) - listOf(Range(8, 12)))
}
data class Range(val start: Int, val end: Int)
operator fun List<Range>.minus(other: List<Range>): List<Range> {
// key is the time, value is the change of "openess" at this time
val events = sortedMapOf<Int, Int>()
forEach { (start, end) ->
events.merge(start, 1, Int::plus)
events.merge(end, -1, Int::plus)
}
other.forEach { (start, end) ->
events.merge(start, -1, Int::plus)
events.merge(end, 1, Int::plus)
}
val result = mutableListOf<Range>()
var currOpeness = 0
var currStart = 0
for ((time, change) in events) {
// we were open and now closing
if (currOpeness == 1 && change < 0) {
result += Range(currStart, time)
}
currOpeness += change
// we were closed and now opening
if (currOpeness == 1 && change > 0) {
currStart = time
}
}
return result
}https://stackoverflow.com/questions/74670791
复制相似问题
腾讯云开发者
