LeetCode--56人の逆順思考を学ぶ

Given a collection of intervals, merge all overlapping intervals.
For example,Given  [1,3],[2,6],[8,10],[15,18] ,return  [1,6],[8,10],[15,18] .
この問題は、まず与えられたテスト配列が秩序化されているわけではないので、私が最初に考えたのは、まず左端に従ってソートすれば、問題を解決することができますが、時間がタイムアウトします.具体的なコードは以下の通りです.

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    public List sort(List intervals){
      int length = intervals.size();
        if(length<=0){
            return intervals;            
        }
        Interval temp = new Interval();
        
        for(int i = 0;i merge(List intervals) {
        List ret = new ArrayList();
        Interval temp = new Interval();
        int length = intervals.size();
        if(length<=0){
            return ret;
            
        }
        intervals = sort(intervals);
        
         temp.start = intervals.get(0).start;
         temp.end = intervals.get(0).end;
       
        
        for(int i=1; i temp.end){
                    ret.add(temp);
                    temp = new Interval();
                    temp.start = intervals.get(i).start;
                    temp.end = intervals.get(i).end;
                   
                }else{
                    temp.end=intervals.get(i).end;
                }
            }
        }
        ret.add(temp);

        return ret;
        
    }
}

そこで私は、私が使っているソート時間が長すぎると思います??だから、どうやって並べ替えないのかと悩んでいましたが、書いてしまい、結果的に再帰的な感覚を利用してしまいました.ラベルを設定します.彼がサブセットに関連しているかどうか、関連しているかどうかはマージされ、新しいサブセットが生成されます.これらのサブセットはマージできますか.できれば、このメソッドを呼び出し続けます.集合が変わらないまで,集合が変わらない基準は配列の長さが変わらないことである.そこで、具体的なコードは以下の通りです.

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
  
    public List merge(List intervals) {
        List ret = new ArrayList();
        int length = intervals.size();
        if(length<=0){
            return ret;            
        }
        int[] tag = new int[length];
        for(int i=0;i end || intervals.get(j).end < start){                    
                    
                    continue;
                }
                
                if(intervals.get(j).start <= start ){
                    start = intervals.get(j).start;
                    if(intervals.get(j).end >= end){
                        end=intervals.get(j).end;
                        tag[i]=1;
                    }
                    
                }else{
                    if( intervals.get(j).end > end){
                        end=intervals.get(j).end;                        
                    }
                }
                if(tag[i]==0){
                    tag[j]=1;
                }
                

            }
            if(tag[i]==0){
                Interval temp = new Interval();
                temp.start=start;
                temp.end=end;
                ret.add(temp);
                tag[i]=1;
            }
            
        }
        while(ret.size()!=intervals.size()){
            intervals=ret;
            ret=merge(intervals);
        }

        return ret;        
        
    }
}

しかし、私が答えを提出した後、私は自分で書いた過程で、私はどうして結果を保存する方面から考えることができないのかと思っていましたが、その時はまだ一つの考えを歩いていて、これを考えていませんでした.提出した後、本当にこのように考えるのがとても力があることに気づきました.コードが短い.コードは以下の通りです:大神からの、

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    public List merge(List intervals) {
        List res = new ArrayList();
        for(int i = 0; i < intervals.size(); i++){
            isoverlap(intervals.get(i), res);
        }
        return res;
        
    }
    
    public void isoverlap(Interval one, List res){
        int size = res.size() - 1;
        int min = one.start, max = one.end;
        for(int i = size; i >= 0; i--){
            Interval now = res.get(i);
            if(now.start > one.end || now.end < one.start){
                continue;
            }else{
                min = Math.min(one.start, Math.min(min, now.start));
                max = Math.max(one.end, Math.max(max, now.end));
                res.remove(i);
            }
        }
        res.add(new Interval(min, max));
            
    }
}

私の思惟はやはりこの1歩を思い付いていないで、とても気がふさいで、ふん、だから記録して、後でこのような考え方をマスターすることを望みます.