# A Divide and Conquer O(nlg(n)) in C#/C++(544 ms, 624 ms)

• This solution is based on MergeSort algorithm. The sorting and merge is done at the same time from the down to the top, instead of sorting first. Implementation is done in C# and C++ with a little bit difference. I'm a little bit surprise that the C# version run faster than the C++ one.

C# version

`````` // Use a merge and sort strategy
public IList<Interval> Merge(IList<Interval> intervals)
{
return MergeSort(intervals);
}

// Merge Sort is based on divide and conquer algorithm: O(nlg(n))
public IList<Interval> MergeSort(IList<Interval> intervals)
{
if (intervals == null || intervals.Count < 2)
return intervals;

// Divide: Split the list in two part
int half = intervals.Count / 2;
List<Interval> inter1 = new List<Interval>();
List<Interval> inter2 = new List<Interval>();
int i = 0;
foreach (Interval inter in intervals)
{
if(inter != null)
{
if (i < half)
{
}
else
{
}

++i;
}
}

// Conquer 1rst half
var result1 = MergeSort(inter1);
// Conquer 2nd half
var result2 = MergeSort(inter2);
//Combine
return Merge(result1, result2);
}

public IList<Interval> Merge(IList<Interval> inter1, IList<Interval> inter2)
{
// Merge intervals 1 and 2
if (inter1 == null || inter1.Count == 0)
return inter2;
else if (inter2 == null || inter2.Count == 0)
return inter1;

List<Interval> results = new List<Interval>();
int n1 = inter1.Count;
int n2 = inter2.Count;
int i = 0, j = 0;
while(i < n1 || j < n2)
{
if(i < n1 && j< n2)
{
var a = inter1[i];
var b = inter2[j];
// compare inter1 and inter2
if(a.start <= b.start)
{
++i;
}
else
{
++j;
}
}
else if(i < n1)
{
++i;
}
else
{
++j;
}
}

return results;
}

private Interval AddOrMergeWithResult(IList<Interval> results, Interval lastInterval, Interval newInterval)
{
// Add the new interval to the results list or merge it with the last interval
if (lastInterval != null)
{
if (newInterval.start > lastInterval.end)
{
// both are disjoint
lastInterval = newInterval;
}
else
{
// Not disjoint, merge both
lastInterval.end = Math.Max(newInterval.end, lastInterval.end);
}
}
else
{
// No comparison needed so just add it
lastInterval = newInterval;
}

return lastInterval;
}
``````

C++ version

``````int AddOrMergeWithResult(vector<Interval>& results, int& lastAddedIntervalIndex, Interval& newInterval)
{
// Add the new interval to the results list or merge it with the last interval
{
if (newInterval.start > lastInterval.end)
{
// both are disjoint
results.push_back(newInterval);
}
else
{
// Not disjoint, merge both
lastInterval.end = fmax((float) newInterval.end,(float) lastInterval.end);
}
}
else
{
// No comparison needed so just add it
results.push_back(newInterval);
}

}
vector<Interval> Merge(vector<Interval>& inter1, vector<Interval>& inter2)
{
// Merge intervals 1 and 2
if (inter1.size() == 0)
return inter2;
else if (inter2.size() == 0)
return inter1;

vector<Interval> results;
int n1 = inter1.size();
int n2 = inter2.size();
int i = 0, j = 0;
while (i < n1 || j < n2)
{
if (i < n1 && j< n2)
{
Interval a = inter1[i];
Interval b = inter2[j];
// compare inter1 and inter2
if (a.start <= b.start)
{
++i;
}
else
{
++j;
}
}
else if (i < n1)
{
++i;
}
else
{
++j;
}
}

return results;
}

// Merge Sort is based on divide and conquer algorithm: O(nlg(n))
vector<Interval> MergeSort(vector<Interval>& intervals)
{
if (intervals.size() < 2)
return intervals;

// Divide: Split the list in two part
int half = intervals.size() / 2;
vector<Interval> inter1;
vector<Interval> inter2;
int i = 0;
for (vector<Interval>::iterator iter = intervals.begin(); iter != intervals.end(); ++iter)
{
Interval inter = *iter;
if (i < half)
{
inter1.push_back(inter);
}
else
{
inter2.push_back(inter);
}

++i;
}

// Conquer 1rst half
vector<Interval> result1 = MergeSort(inter1);
// Conquer 2nd half
vector<Interval> result2 = MergeSort(inter2);
//Combine
return Merge(result1, result2);
}

// Use a merge and sort strategy
vector<Interval> merge(vector<Interval>& intervals)
{
return MergeSort(intervals);
}``````

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