C# Binary search solution


  • 0

    C# is not supported for this problem. But I thought it was a nice problem. So I solved it anyway. I have used a List to track the Intervals and binary search to locate the location of the interval for the given val.

    The index can be for an interval that either contains the given value, is before the given value or contains elements after the given value.

    If the given value should be in the left of the chosen interval, find the previous interval. The value can either be added to the end of the previous interval(if prev.End+1 == val) or the start of the chosen interval (cur.Start -1 == val) or inserted between the two as a new interval

    Similar changes are needed when the value needs to be to the right of the chosen interval.

    If the interval was not inserted, we also need to check if (prev, cur) or (cur, next) can be merged together.

       public class Interval
       {
            public int Start { get; set; }
            public int End { get; set; }
            public Interval(int start, int end)
            {
                this.Start = start;
                this.End = end;
            }
        }
    
        public class SummaryRanges
        {
            List<Interval> ranges;
            public SummaryRanges()
            {
                this.ranges = new List<Interval>();
            }
    
            public SummaryRanges(Interval[] intervals)
            {
                this.ranges = new List<Interval>(intervals);
            }
            
            public void AddNum(int val)
            {
                // Find insert position.
                int idx = GetInsertIndex(val);
                // Candidate interval
                if (idx < 0)
                {
                    idx = 0;
                }
    
                if (idx >= this.ranges.Count)
                {
                    idx = this.ranges.Count - 1;
                }
                
                if (this.ranges.Count == 0)
                {
                    this.ranges.Add(new Interval(val, val));
                    return;
                }
    
                Interval c = this.ranges.ElementAt(idx);
                if (c.Start <= val && c.End >= val)
                {
                    return;
                }
                else
                {
                    // Check if the number goes to the left or right of the chosen interval.
                    // -1 is for left and +1 is for right;
                    List<int> toMerge = new List<int>();
                    int mrgOffset = c.Start > val ? -1 : 1;
                    if (mrgOffset == -1)
                    {
                        if (idx == 0)
                        {
                            if (val + 1 == c.Start)
                            {
                                c.Start = val;
                            }
                            else
                            {
                                this.ranges.Insert(idx, new Interval(val, val));
                            }
                        }
                        else
                        {
                            Interval prev = this.ranges.ElementAt(idx + mrgOffset);
                            bool merge = false;
                            if (prev.End + 1 == val)
                            {
                                prev.End = val;
                                merge = true;
                            }
                            else if (c.Start -1 == val)
                            {
                                c.Start = val;
                                merge = true;
                            }
                            else
                            {
                                this.ranges.Insert(idx, new Interval(val, val));
                            }
    
                            // If the prev and current one have no elements in between
                            if (merge && c.Start- prev.End <= 1)
                            {
                                prev.End = c.End;
                                this.ranges.RemoveAt(idx);
                            }
                            
                        }
                    }
                    else
                    {
                        if (idx == this.ranges.Count - 1)
                        {
                            if (val - 1 == c.End)
                            {
                                c.End = val;
                            }
                            else
                            {
                                this.ranges.Insert(idx + mrgOffset, new Interval(val, val));
                            }
                        }
                        else
                        {
                            Interval next = this.ranges.ElementAt(idx + mrgOffset);
                            bool merge = false;
                            if (next.Start - 1 == val)
                            {
                                next.Start = val;
                                merge = true;
                            }
                            else if (c.End - 1 == val)
                            {
                                c.End = val;
                                merge = true;
                            }
                            else
                            {
                                this.ranges.Insert(idx + mrgOffset, new Interval(val, val));
                            }
    
                            // The interval either needs to be merged or a new one needs to be inserted at idx.
                            if (merge && next.Start - c.End <= 1)
                            {
                                next.Start = c.Start;
                                this.ranges.RemoveAt(idx);
                            }
                        }
                    }
                }
            }
    
            public List<Interval> GetIntervals()
            {
                return this.ranges;
            }
    
            private int GetInsertIndex(int val)
            {
                int low = 0;
                int high = ranges.Count() - 1;
                while (low < high)
                {
                    int middle = low + (high - low) / 2;
                    Interval midInterval = this.ranges.ElementAt(middle);
                    if (midInterval.Start <= val && midInterval.End >= val)
                    {
                        // This is the correct interval.
                        return middle;
                    }
                    else if (val < midInterval.Start)
                    {
                        high = middle - 1;
                    }
                    else
                    {
                        low = middle + 1;
                    }
                }
    
                return low;
            }
        }
    

Log in to reply
 

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