package com.tolchev.algo.array

class NonOverlappingIntervals {
    fun eraseOverlapIntervals(intervals: Array<IntArray>): Int {
        intervals.sortWith { a, b -> a[1].compareTo(b[1]) }

        var maxFinishTime = intervals[0][1]
        var removeCount = 0

        for (i in 1 ..< intervals.size)
            if (intervals[i][0] < maxFinishTime){
                removeCount++
            } else{
                maxFinishTime = intervals[i][1]
            }

        return removeCount
    }
}
class NonOverlappingIntervalsSlow {
    fun eraseOverlapIntervals(intervals: Array<IntArray>): Int {
        var allIntersection = Array<MutableSet<Int>>(intervals.size){mutableSetOf()}

        intervals.sortWith { a, b -> a[0].compareTo(b[0]) }

        for (i1 in 0 ..< intervals.size-1){
            var i2 = i1 +1

            while (i2 < intervals.size && (intervals[i2][0] < intervals[i1][1])){
                allIntersection[i1].add(i2)
                allIntersection[i2].add(i1)
                i2++
            }
        }

        var removeCount = 0

        var i1 = 0


        while (i1 < intervals.size){

            var i2 = i1 + 1

            while ((allIntersection[i1]?.size ?: 0) != 0
                && (allIntersection[i2]?.size ?: 0) != 0
                && intervals[i2][0] < intervals[i1][1])
            {
                if (allIntersection[i1]!!.size > allIntersection[i2]!!.size){
                    removeInterval(i1, allIntersection)
                }
                else{
                    removeInterval(i2, allIntersection)
                    i2++
                }

                removeCount++
            }

            i1++
        }

        return removeCount
    }

    private fun removeInterval(index: Int, allIntersection : Array<MutableSet<Int>>) {
        var intersections = allIntersection[index]!!

        for (intersection in intersections) {
            allIntersection[intersection]!!.remove(index)
        }

        intersections.clear()
    }
}