Merging non overlapping intervals

Given a set of non overlapping intervals
Example 1: (1,4) (6,10) (14, 19) and another interval (13, 17) merge them as (1,4) (6,10) (13,19)

Example 2: (1,5) (6, 15) (20, 21) (23, 26) (27, 30) (35, 40)
New interval (14, 33)
Output should be
(1,5) (6, 33) (35, 40)

This is because the new interval overlaps with (6, 15) (20, 21) (23, 26) (27, 30)

using System;
using System.Collections;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            string discreteInterval = "(1,5) (6, 15) (20, 21) (23, 26) (27, 30) (35, 40)";
            string newInterval = "(14, 33)";
            ArrayList rangeList = getRangeList(discreteInterval);
            ArrayList newRangeList = getRangeList(newInterval);
            //Print the original interval
            Console.WriteLine("Original Interval");
            for (int i = 0; i < rangeList.Count; i += 2)
            {
                Console.WriteLine(rangeList[i].ToString() + " -- " + rangeList[i + 1].ToString());
            }
            //Print the original interval
            Console.WriteLine("");
            Console.WriteLine("New Interval");
            for (int i = 0; i < newRangeList.Count; i += 2)
            {
                Console.WriteLine(newRangeList[i].ToString() + " -- " + newRangeList[i + 1].ToString());
            }
            int lowerLimit = int.Parse(newRangeList[0].ToString());
            int upperLimit = int.Parse(newRangeList[1].ToString());
            int lowerLimitBound = limitBound(true, lowerLimit, rangeList);
            int upperLimitBound = limitBound(false, upperLimit, rangeList);

            if (lowerLimitBound == upperLimitBound)
            {
                rangeList.Insert(lowerLimitBound, upperLimit);
                rangeList.Insert(lowerLimitBound, lowerLimit);
            }
            else if (lowerLimitBound % 2 == 0 && upperLimitBound % 2 != 0)
            {
                rangeList.Insert(lowerLimitBound, lowerLimit);
                rangeList.RemoveAt(lowerLimitBound + 1);
                int i = lowerLimitBound + 1;
                for (int count = lowerLimitBound + 1; count < upperLimitBound; count++)
                {
                    rangeList.RemoveAt(i);
                }
            }
            else if (lowerLimitBound % 2 != 0 && upperLimitBound % 2 == 0)
            {
                rangeList.Insert(upperLimitBound, upperLimit);
                int i = lowerLimitBound;
                for (int count = lowerLimitBound; count < upperLimitBound; count++)
                {
                    rangeList.RemoveAt(i);
                }
            }
            else if (lowerLimitBound % 2 != 0 && upperLimitBound % 2 != 0)
            {
                int i = lowerLimitBound;
                for (int count = lowerLimitBound; count < upperLimitBound; count++)
                {
                    rangeList.RemoveAt(i);
                }
            }
            else if (lowerLimitBound % 2 == 0 && upperLimitBound % 2 == 0)
            {
                rangeList.Insert(lowerLimitBound, lowerLimit);
                rangeList.Insert(upperLimitBound + 1, upperLimit);
                int i = lowerLimitBound + 1;
                for (int count = lowerLimitBound + 1; count <= upperLimitBound; count++)
                {
                    rangeList.RemoveAt(i);
                }
            }
            //Print the merged interval
            Console.WriteLine("");
            Console.WriteLine("Merged Interval");
            for (int i = 0; i < rangeList.Count; i += 2)
            {
                Console.WriteLine(rangeList[i].ToString() + " -- " + rangeList[i + 1].ToString());
            }
        }
        public static int limitBound(bool lower, int num, ArrayList rangeList)
        {
            //Determine the upper limit for specified number
            int flag = -1;
            for (int i = 0; i < rangeList.Count; i++)
            {
                if ((lower && num > int.Parse(rangeList[i].ToString())) || (!lower && num >= int.Parse(rangeList[i].ToString())))
                {
                    continue;
                }
                else
                {
                    flag = i;
                    break;
                }
            }
            int limit = flag;
            if (flag == -1)
            {
                if (num < int.Parse(rangeList[0].ToString()))
                {
                    limit = 0;
                }
                else
                {
                    limit = rangeList.Count;
                }
            }
            return limit;
        }
        public static ArrayList getRangeList(string str)
        {
            ArrayList rangeList = new ArrayList();
            string tempStr = "";
            string sign = "";
            for (int i = 0; i < str.Length; i++)
            {
                if (char.IsDigit(str[i]))
                {
                    tempStr = tempStr + str[i];
                }
                else if (str[i] == '-')
                {
                    sign = "-";
                }
                else
                {
                    if (tempStr != "")
                    {
                        if (sign == "-")
                        {
                            tempStr = "-" + tempStr;
                            sign = "";
                        }
                        rangeList.Add(int.Parse(tempStr));
                        tempStr = "";
                    }
                }
            }
            return rangeList;
        }
    }
}

Output:
=======
Original Interval
1 -- 5
6 -- 15
20 -- 21
23 -- 26
27 -- 30
35 -- 40
New Interval
14 -- 33
Merged Interval
1 -- 5
6 -- 33
35 -- 40
Press any key to continue . . .
Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s