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)
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
}
2条答案
按热度按时间30byixjq1#
下面是一个查找不相交时间范围的简单方法:
创建所有时间范围的列表(例如,在第一个示例中,列表为[7-12 a.m.,2-10 a.m.])按每个范围的开始时间对列表进行排序(在第一个示例中,列表为[7-12 a.m.,2-10 a.m.])循环遍历范围列表,并将每个范围与下一个范围进行比较,查看它们是否相交。如果相交,请将两个范围合并为一个范围。
在第一个示例中,第一个范围(7- 12a.m.)将与第二个范围(2- 10a.m.)进行比较,并且由于它们相交,因此它们将合并为一个范围(7- 10a.m.)。
继续在列表中循环并合并区域,直到再也找不到相交的区域。在第一个示例中,合并前两个区域后,生成的列表将是[7-10 a.m.,11-12 a.m.,2-5 p.m.]。
示例实现:
并这样称呼它:
在第一个范例中,产生的不相交范围清单会是[7-10 a.m.,11-12 a.m.,2-5 p.m.]。在第二个范例中,产生的清单会是[7-10 a.m.,5-10 p.m.]。
fwzugrvs2#
听起来像是一个很常见的情况,我怀疑有一些现有的算法,但没有出来的顶部我的头。
我的想法是首先将两个范围列表转换成一个按时间排序的开始/结束“事件”列表。(
-1
)。收盘范围的开始也会降低“开放性”,而结束则会增加“开放性”。然后,我们按时间顺序迭代事件。保持当前“开放”水平的信息。当“开放”水平为1
时,这意味着我们处于开盘区间的中间,但不在收盘区间内,因此我们完全开放。假设这两个范围列表最初都是正确排序的,就像你的例子一样,我相信它在线性时间内应该是可行的,什至没有这个中间事件列表。然而,这样的实现要覆盖所有可能的状态会相当复杂,所以我决定采用一个更简单的解决方案,我相信是
O(n * log(n))
。而且,这个实现要求开始的范围不能相互重叠。收盘价也一样: