kotlin 正在获取非相交范围之间的时间范围

ldfqzlk8  于 2022-12-04  发布在  Kotlin
关注(0)|答案(2)|浏览(158)

我有以下时间表:
第一个
我试着用减和减的方法来计算范围,但没有成功。一个棘手的部分可能是以下情况
第一次
对Kotlin实施有什么想法?
我尝试对范围进行减和减方法,但不起作用

30byixjq

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.]。
示例实现:

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 a.m.,11-12 a.m.,2-5 p.m.]。在第二个范例中,产生的清单会是[7-10 a.m.,5-10 p.m.]。

fwzugrvs

fwzugrvs2#

听起来像是一个很常见的情况,我怀疑有一些现有的算法,但没有出来的顶部我的头。
我的想法是首先将两个范围列表转换成一个按时间排序的开始/结束“事件”列表。(-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
}

相关问题