Runtime Error for large input


  • 1
    A
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        ArrayList<Interval> result = new ArrayList();
        if (intervals.isEmpty()) {
            return result;
        }
        Collections.sort(intervals, new Comparator<Interval>(){
            public int compare(Interval int1, Interval int2) {
                if (int1.start < int2.start) {
                    return -1;
                }
                if (int1.start == int2.start && int1.end <= int2.end) {
                    return -1;
                }
                return 1;
            }
        });
        
        int start = intervals.get(0).start;
        int end = intervals.get(0).end;
        for (int i = 1; i < intervals.size(); ++i) {
            Interval interval = intervals.get(i);
            if (interval.end < start) {
                result.add(interval);
            }
            else if (interval.start > end) {
                result.add(new Interval(start, end));
                start = interval.start;
                end = interval.end;
            }
            else {
                start = Math.min(start, interval.start);
                end = Math.max(end, interval.end);
            }
        }
        result.add(new Interval(start, end));
        return result;
    }
    

    I got Runtime Error for following test case, but I have no idea why it failed, could someone help me out? I copy/paste the code and compile&run it with same test case, no error:

    [[74,78],[61,63],[46,50],[51,54],[50,50],[60,64],[39,42],[25,27],[91,95],[14,16],[85,85],[5,7],[45,46],[45,49],[66,66],[73,73],[25,26],[25,26],[45,48],[67,67],[63,65],[82,84],[90,92],[47,49],[3,4],[1,5],[64,66],[73,77],[90,94],[20,21],[84,87],[48,49],[80,80],[85,85],[53,55],[21,23],[31,34],[71,75],[62,65],[8,9],[32,33],[7,8],
    ...(I truncated it as it exceeds the maximum length)
    ,[44,45],[40,40],


  • 0
    H

    change to

    Collections.sort(intervals, new Comparator<Interval>(){
            public int compare(Interval int1, Interval int2) {
               return int1.start - int2.start;
            }
    });
    

    will be ok! maybe sort take too much time?


  • 0

    Your code throws the below exception:

    Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!

    This thread would probably help you understanding why:
    http://stackoverflow.com/questions/11441666/java-error-comparison-method-violates-its-general-contract


Log in to reply
 

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