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


  • 0
    O

    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)
              {
                inter1.Add(inter);
              }
              else
              {
                inter2.Add(inter);
              }
    
              ++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;
          Interval lastAddedInterval = null;
          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)
    			    {
                lastAddedInterval = AddOrMergeWithResult(results, lastAddedInterval, a);
                ++i;
              }
    			    else
    			    {
                lastAddedInterval = AddOrMergeWithResult(results, lastAddedInterval, b);
                ++j;
    			    }
    		    }
    		    else if(i < n1)
    		    {
              AddOrMergeWithResult(results, lastAddedInterval, inter1[i]);
    			    ++i;
    		    }
    		    else
    		    {
              AddOrMergeWithResult(results, lastAddedInterval, inter2[j]);
    			    ++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
              results.Add(newInterval);
              lastInterval = newInterval;
            }
            else
            {
              // Not disjoint, merge both
              lastInterval.end = Math.Max(newInterval.end, lastInterval.end);
            }
          }
          else
          {
            // No comparison needed so just add it
            results.Add(newInterval);
            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 (lastAddedIntervalIndex > -1)
      {
        Interval lastInterval = results.at(lastAddedIntervalIndex);
        if (newInterval.start > lastInterval.end)
        {
          // both are disjoint
          results.push_back(newInterval);
          ++lastAddedIntervalIndex;
        }
        else
        {
          // Not disjoint, merge both
          lastInterval.end = fmax((float) newInterval.end,(float) lastInterval.end);
          results[lastAddedIntervalIndex] = lastInterval;
        }
      }
      else
      {
        // No comparison needed so just add it
        results.push_back(newInterval);
        lastAddedIntervalIndex = 0;
      }
    
      return lastAddedIntervalIndex;
    }
    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;
      int lastAddedIntervalIndex = -1;
      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)
          {
            lastAddedIntervalIndex = AddOrMergeWithResult(results, lastAddedIntervalIndex, a);
            ++i;
          }
          else
          {
            lastAddedIntervalIndex = AddOrMergeWithResult(results, lastAddedIntervalIndex, b);
            ++j;
          }
        }
        else if (i < n1)
        {
          AddOrMergeWithResult(results, lastAddedIntervalIndex, inter1[i]);
          ++i;
        }
        else
        {
          AddOrMergeWithResult(results, lastAddedIntervalIndex, inter2[j]);
          ++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);
    }

Log in to reply
 

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