Why sort? Why extra memory space? Challenge me if you have a more elegant solution.


  • -24
    K
    public class Solution 
    {
        public List<Interval> merge(List<Interval> intervals) 
        {
            if(intervals.size()<2) return intervals;
            int count=0;
            //If no more merge can be done, 
            //then counting when traversing the list through will give out the size of list.
            while(count<intervals.size())
            {
                int before=intervals.size();
                //My algorithm guarantee the first element of the list is the one hasn't been checked.
                Interval temp=intervals.remove(0);
                int a=temp.start, b=temp.end;
                for(int i=0; i<intervals.size(); i++)
                {
                    temp=intervals.get(i);
                    int c=temp.start, d=temp.end;
                    if(b>=c&&d>=a)
                    {
                        intervals.remove(i);
                        i--;  //i-- is crucial since the list shrunk after removal.
                        a=Math.min(a,c);
                        b=Math.max(b,d);
                    }
                }
                //Putting temporarily merged interval at the end. 
                intervals.add(new Interval(a,b));
                if(before==intervals.size())    count++;
                else count=0;
            }
            return intervals;
        }
    }

  • 5
    Y

    Ask yourself a simple question: what is the time complexity of this smart algorithm? Then you will know why people sort.


  • 0
    K

    Show me ur code and runtime. If it's written in c++, I'll re-write mine to compare with urs.


  • 0
    Y

    First of all, allow me to say that the time complexity of your solution is O(n^2), which is worse than O(nlog n). If you sort the input at first, which takes O(nlog n), then you can liner scan the list and do the merge in O(n) time. Thus the final time complexity is O(n log n ). The merge can be done in the sort process, if you write the sort by yourself. Secondly, the runtime on leetcode is meaninless. As you can see, the runtime of the same code can be various even submiting in the same time period


  • 0
    K

    I appreciate your comments, but I have to say that, for many cases, two loops don't necessarily mean O(n^2). Let k be the length of of the answer list of non-overlapping intervals denoted by S, then in the first run, S0 will consume all those intervals overlapping with it, meaning that, in the second run, less than n intervals needed to be compared. I do shared your opinion about O(n^2) in the worst input scenario, in which any two intervals are disjoint, so it takes n^2. However, in most input scenarios, the first few runs can prune out most of n intervals within the input, meaning that we are very likely to have a constant*n run-time. By the way, with the respect of memory usage, mine does the best.


  • 1
    Y

    "for many cases, two loops don't necessarily mean O(n^2)" indicates that you didn't understand the big O operation and the meaning of time complexity correctly. Your statement is wrong.


  • 0
    L

    Well, I have to say most, if not every, people have a more elegant solution...


  • 0
    H

    Idea is good. Solution can be more elegant. Anyway this solution beats 95% other solutions!


  • 0

    I had similar thought at the very first. And solution without sorting ends up being extremely fast (Beat 96~98%)... But it should be O(N^2) indeed, right? So I assume that is the test data set problem maybe it's not large enough?

        public List<Interval> merge(List<Interval> intervals) {
            List<Interval> result = new ArrayList<>();
            for (Interval interval : intervals)
                doMergeOne(result, interval);
            return result;
        }
        
        private void doMergeOne(List<Interval> merged, Interval interval) {
            int i = 0;
            for (; i < merged.size() && merged.get(i).end < interval.start; i++);
            while (i < merged.size() && merged.get(i).start <= interval.end) {
                interval = new Interval(Math.min(merged.get(i).start, interval.start),
                                        Math.max(merged.get(i).end, interval.end));
                merged.remove(i);
            }
            merged.add(i, interval);
        }
    

Log in to reply
 

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