美文网首页
LeetCode之Insert Interval(Kotlin)

LeetCode之Insert Interval(Kotlin)

作者: 糕冷羊 | 来源:发表于2019-03-26 20:36 被阅读0次

    问题:
    Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
    You may assume that the intervals were initially sorted according to their start times.

    Example 1:
    
    Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
    Output: [[1,5],[6,9]]
    Example 2:
    
    Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
    Output: [[1,2],[3,10],[12,16]]
    Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
    

    方法:
    先创建结果list,然后添加newInterval作为基准,然后遍历intervals所有元素,区间在newInterval左边的区间add到左边,区间在newInterval右边的区间add到右边,如果区间有交叠则与newInterval做合并,最后遍历结束即为结果。

    具体实现:

    class InsertInterval {
        // Definition for an interval.
        class Interval(var start: Int = 0, var end: Int = 0) {
            override fun toString(): String {
                return "Interval(start=$start, end=$end)"
            }
        }
    
        fun insert(intervals: List<Interval>, newInterval: Interval): List<Interval> {
            val result = mutableListOf<Interval>()
            result.add(newInterval)
            for (interval in intervals) {
                if (interval.end < newInterval.start) {
                    result.add(result.lastIndex, interval)
                } else if (interval.start > newInterval.end) {
                    result.add(result.lastIndex+1, interval)
                } else if (interval.start <= newInterval.start && interval.end >= newInterval.end ) {
                    newInterval.start = interval.start
                    newInterval.end = interval.end
                } else if (interval.start <= newInterval.start && interval.end < newInterval.end) {
                    newInterval.start = interval.start
                } else if (interval.start > newInterval.start && interval.end >= newInterval.end) {
                    newInterval.end = interval.end
                }
            }
            return result
        }
    }
    
    fun main(args: Array<String>) {
        val intervals = listOf(InsertInterval.Interval(2, 6), InsertInterval.Interval(7, 9))
        val newInterval = InsertInterval.Interval(15, 18)
        val insertInterval = InsertInterval()
        for (ele in insertInterval.insert(intervals, newInterval)) {
            println(ele)
        }
    }
    

    有问题随时沟通

    具体代码实现可以参考Github

    相关文章

      网友评论

          本文标题:LeetCode之Insert Interval(Kotlin)

          本文链接:https://www.haomeiwen.com/subject/mzonvqtx.html