[Google Question] Non-overlapping interval

Problem: Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Example:

Input: [[1,2],[2,3],[2,4]]
Output: 1
Explanation: [2,3] or [2,4] can be removed to make intervals non-overlapping.

Approach: We can sort the intervals based on start point of interval. Once we sort this array, the problem becomes simpler. We can maintain two pointers compareIndex and iterator. \ We can then follow below steps:

• result = 0
• compareIndex = 0;
• FOR iterator = 1 to n
• IF intervals[compareIndex ][1] > intervals[iterator ][0] // overlap
• result = result + 1
• IF intervals[compareIndex ][1] > intervals[iterator ][1] // Remove the record with bigger end
• compareIndex = iterator
• ELSE
• compareIndex = iterator
• RETURN result

That's all!

Implementation in C#:

    public int EraseOverlapIntervals(int[][] intervals)

    {

        int length = intervals?.Length ?? 0;

        if (length <= 1)

        {

            return 0;

        }

        Array.Sort(intervals, (i1, i2) => {

            int retVal = i1[0].CompareTo(i2[0]);

            if (retVal == 0)

            {

                return i1[1].CompareTo(i2[1]);

            }

            return retVal;

        });

        int count = 0;

        int compareIndex = 0;

        for (int i = 1; i < length; ++i)

        {

            if (intervals[compareIndex][1] > intervals[i][0])

            {

                ++count;

                if (intervals[compareIndex][1] > intervals[i][1])

                {

                    compareIndex = i;

                }

            }

            else

            {

                compareIndex = i;

            }

        }

        return count;

    }

Complexity: O(nlogn)