Getting Time range between non intersecting ranges-CodePudding

I have the following timelines :


7 a.m --------------------- 12 a.m.  2 am .................. 10 a.m
         10-------11                        3------5
            closed                          closed

the output should be the non-intersecting time ranges:
 7-10 a.m, 11 -12 a.m, 2-3 p.m, 5-10 p.m

I tried to minus and subtract method for Ranges but didn't work A tricky part could be the following case


7 a.m --------------------- 12 a.m.  2 am .................. 10 a.m
          10----------------------------------------5
                              closed

the output should be the non-intersecting time ranges:
 7-10 a.m, 5-10 p.m

Any Idea for kotlin implementation?

I tried to minus and subtract method for Ranges but didn't work

CodePudding user response：

Here's a simple approach to find the non-intersecting time ranges:

Create a list of all the time ranges (for example, in the first example, the list would be [7-12 a.m., 2-10 a.m.]) Sort the list by the start time of each range (in the first example, the list would be [7-12 a.m., 2-10 a.m.]) Loop through the list of ranges and compare each range with the next range to see if they intersect. If they do, merge the two ranges into one range.

In the first example, the first range (7-12 a.m.) would be compared with the second range (2-10 a.m.), and since they intersect, they would be merged into one range (7-10 a.m.).

Continue looping through the list and merging ranges until no more intersecting ranges are found. In the first example, after merging the first two ranges, the resulting list would be [7-10 a.m., 11-12 a.m., 2-5 p.m.].

Sample implementation:

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
}

And call it like this:

val ranges = listOf(7 to 12, 2 to 10)
val nonIntersectingRanges = findNonIntersectingRanges(ranges)

In the first example, the resulting list of non-intersecting ranges would be [7-10 a.m., 11-12 a.m., 2-5 p.m.]. In the second example, the resulting list would be [7-10 a.m., 5-10 p.m.].

CodePudding user response：

Sounds like a pretty common case and I suspect there are some existing algorithms for it, but nothing comes out of top of my head.

My idea is to first transform both lists of ranges into a single list of opening/closing "events", ordered by time. The start of an opening range increases the "openess" by 1 while its end decreases it (-1). Start of a closing range also decreases "openess" while its end increases it. Then we iterate the events in the time order, keeping the information on what is the current "openess" level. Whenever the "openess" level is 1, that means we are in the middle of an opening range, but not inside a closing range, so we are entirely open.

Assuming both lists of ranges are initially properly ordered, as in your example, I believe it should be doable in linear time and even without this intermediary list of events. However, such implementation would be pretty complicated to cover all possible states, so I decided to go with a simpler solution which is I believe O(n * log(n)). Also, this implementation requires that opening ranges do not overlap with each other, the same for closing 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
}