Best case O(n) and worse case O(n^2) C++ solution, fast for heavily overlapping intervals


  • 0
    M

    While sorting the array is the standard answer, there are still cases where brute-force algorithms are useful. I came up with this thought when I accidently miswrote the '<' sign into the '<=' sign in my sorting comparator and failed the test due to time limit exceed. Actually, if N is very large but the range of each interval is limited (e.g. from -500 to +500), these intervals overlap heavily. In other words, the number of distinct intervals (after processing the kth interval) linearly scales with k at the beginning, but will converge to a constant with the increase of k. In that case, the time complexity of my brute-force algorithm can be reduced to O(N).

    class Solution {
    public:
        vector<Interval> merge(vector<Interval>& intervals) {
            int n = intervals.size();
            list<Interval> intervalSet;
            vector<Interval> res;
            
            for (int i = 0; i < n; i++)
            {
                auto myInterval = intervals[i];
                
                for (auto it = intervalSet.begin(); it != intervalSet.end(); )
                {
                    auto currInterval = *it;
                    
                    if (haveIntersection(currInterval, myInterval))
                    {
                        merge2Intervals(currInterval, myInterval);
                        it = intervalSet.erase(it);
                    }
                    else
                        it++;
                }
                
                intervalSet.push_back(myInterval);
            }
            
            for (auto& interval : intervalSet)
                res.push_back(interval);
                
            return res;
        }
        
        bool haveIntersection(Interval a1, Interval a2)
        {
            return (a2.start >= a1.start && a2.start <= a1.end) ||
                   (a2.end >= a1.start && a2.end <= a1.end) ||
                   (a1.start >= a2.start && a1.start <= a2.end) ||
                   (a1.end >= a2.start && a1.end <= a2.end);
        }
        
        void merge2Intervals(Interval& strt, Interval& dest)
        {
            dest.start = min(strt.start, dest.start);
            dest.end = max(strt.end, dest.end);
        }
    };

Log in to reply
 

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