Fast c# solution


  • 0
    P

    **57. Insert Interval **


    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:
    Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

    Example 2:
    Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

    This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].


    Approach: Efficient Solution

    ** Logic **

    There are 3 cases with the new interval that to be inserted.

    1. New interval overlaps with the existing interval
    2. New interval does not overlap: it is the first interval
    3. New interval does not overlap: it is the last interval
    • Case 1: interval overlaps:
      • Start with the first overapped interval, let's call it startIntr;
      • find all the subsequent intervals that overlap with the new interval, Let's call it
        endIntr;
      • create insert new interval such that:
        • insIntr.start = min (startIntr.start , newInterval.start);
        • insIntr.end = max (endIntr.end, newIntr.end);
        • insert insIntr;
    • Case 2: New interval does not overlap: it is the first interval
      • For this, check if newInterval.end is smaller that intervals[i] and it is not
        already inserted
      • If the above conditions is true, insert the new interval
    • Case 3: New interval does not overlap: it is the last interval
      • If new interval is not get added, it must be the last interval

    C#

    /**
     * Definition for an interval.
     * public class Interval {
     *     public int start;
     *     public int end;
     *     public Interval() { start = 0; end = 0; }
     *     public Interval(int s, int e) { start = s; end = e; }
     * }
     */
    public class Solution {
    
        // returns min
        private int min(int a, int b)
        {
            return a<b?a:b;
        }
    
        // returns max
        private int max(int a, int b)
        {
            return a<b?b:a;
        }
    
        //
        // check if interval a and b are overlapping with each other
        //
        private bool bOverlapped(Interval a, Interval b)
        {
            return !(a.end < b.start || a.start > b.end );
        }
        
        public IList<Interval> Insert(IList<Interval> intervals, Interval newInterval) {
            IList intr = new List<Interval>();
            bool bFlag = false;
            int i = 0;
    
            while(i < intervals.Count)
            {
                // Case 1: Find overlapping intervals
                if(bOverlapped(newInterval, intervals[i]) == true)
                {
                    // c is first interval which overlaps with newInterval
                    Interval c = intervals[i];
    
                    // find subsequent overlapping intervals
                    while(i<intervals.Count && bOverlapped(newInterval, intervals[i])) 
                      i++;
    
                    // we have found the last overapped interval at i-1
                    c.start = min(c.start, newInterval.start);
                    c.end   = max(newInterval.end, intervals[i-1].end);
                    intr.Add(c);
    
                    // mark flag as true. it indicates that interval is added
                    bFlag = true;
                }
                // Case 2: New interval does not overlap: it is the first interval
                else if (newInterval.end < intervals[i].end && bFlag == false)
                {
                    // Add new interval if it is not already added
                    intr.Add(newInterval);
                    intr.Add(intervals[i++]);
                    bFlag = true;
                }
                else
                    intr.Add(intervals[i++]);
            }
    
            // bFlag == false implies new interval is not added. this means 3rd Case
            if (bFlag == false)
                intr.Add(newInterval);
    
            return (IList<Interval>)intr;
        }
    }
    

    Complexity Analysis

    • Time complexity : (n).

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.