1288.remove-covered-intervals.md

1288. Remove Covered Intervals

TODO: Check the "Solution" section on LeetCode.

Greedy

To check if an interval is covered by another interval, we need to compare the start and end of the intervals efficiently. We can sort the intervals by the start time ascending, then the end time descending, and then iterate through the intervals to check if the current interval is covered by the previous interval.

1, 2, 3, 4, 5, 6, 7, 8, 9, 10
|--------------| // previous interval

// case 1. Same start, end <= previous.end
|--------|
|--------|
|----|

// case 2. previous.start < start, end <= previous.end
   |--------|

// case 3. previous.start < start, previous.end < end
       |--------------| // It will be a new remaining interval
       |---------|

// case 4. non-overlapping, same as case 3
                          |----|

fun removeCoveredIntervals(intervals: Array<IntArray>): Int {
    val n = intervals.size
    intervals.sortWith(compareBy<IntArray> { it[0] }.thenByDescending { it[1] })
    var remaining = 1
    var previous = intervals.first()
    var i = 1
    while (i < n) {
        // case 1. start == previous.start, end <= previous.end
        while (i < n && previous[0] == intervals[i][0] && intervals[i][1] <= previous[1]) {
            i++
        }

        // case 2. previous.start < start, end <= previous.end
        while (i < n && previous[0] < intervals[i][0] && intervals[i][1] <= previous[1]) {
            i++
        }

        // case 3. preivous.start < start, previous.end < end
        if (i < n && previous[0] < intervals[i][0] && previous[1] < intervals[i][1]) {
            previous = intervals[i]
            remaining++
            i++
        }
    }
    return remaining
}