Given a sequence of intervals, return the max overlapping interval

maxOverlapInterval

using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] intervalArray = { 5, 11, 6, 18, 2, 5, 3, 12 };
            int[] startPosition = new int[intervalArray.Length / 2];
            int[] endPosition = new int[intervalArray.Length / 2];
            //Initializing start and end position arrays
            int startPointer = 0, endPointer = 0;
            for (int i = 0; i < intervalArray.Length; i++)
            {
                if (i % 2 == 0)
                {
                    startPosition[startPointer++] = intervalArray[i];
                }
                else
                {
                    endPosition[endPointer++] = intervalArray[i];
                }
            }
            //Sort the start and end arrays
            Array.Sort(startPosition);
            Array.Sort(endPosition);
            Array.Sort(intervalArray);
            int[] differentialArray = new int[intervalArray.Length];
            int counter = 0, count = 0, maxCount = 0;
            //Merge sort start and end position arrays
            for (int i = 0, j = 0; i < startPosition.Length || j < endPosition.Length;)
            {
                if (i < startPosition.Length && j < endPosition.Length)
                {
                    if (startPosition[i] < endPosition[j])
                    {
                        differentialArray[counter++] = ++count;
                        if (maxCount < count)
                        {
                            maxCount = count;
                        }
                        i++;
                    }
                    else
                    {
                        differentialArray[counter++] = --count;
                        j++;
                    }
                }
                else if (i < startPosition.Length)
                {
                    differentialArray[counter++] = ++count;
                    if (maxCount < count)
                    {
                        maxCount = count;
                    }
                    i++;
                }
                else
                {
                    differentialArray[counter++] = --count;
                    j++;
                }
            }
            //Display the max overlap interval
            Console.WriteLine("Max overlap count = " + maxCount);
            ArrayList al = new ArrayList(); //Using this array list for merging continuous intervals
            for (int i = 0; i < differentialArray.Length - 1; i++)
            {
                if (differentialArray[i] == maxCount)
                {
                    if (al.Count != 0 && (int)al[al.Count - 1] == intervalArray[i])
                    {
                        al[al.Count - 1] = intervalArray[i + 1];
                    }
                    else
                    {
                        al.Add(intervalArray[i]);
                        al.Add(intervalArray[i + 1]);
                    }
                }
            }
            Console.Write("Max overlap interval = ");
            for (int i = 0; i < al.Count - 1; i+=2)
            {
                Console.Write("[" + al[i] + ", " + al[i + 1] + "] ");
            }
            Console.WriteLine();
        }
    }
}

Output
=======
Max overlap count = 3
Max overlap interval = [6, 11]
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