ネクタイのLintCode問題の答え-30.挿入区間

9602 ワード

ネクタイのLintCode問題の答え-30.挿入区間
目次
  • 30. 挿入区間
  • 感謝
  • 30.挿入区間
    重複のない区間開始端点に従ってソートされた区間リストを与えます.
    リストに新しい区間を挿入し、リスト内の区間が秩序正しく重複していないことを確認します(必要に応じて区間をマージできます).
    サンプル1:
    入力:(2,5)into[(1,2),(5,9)]出力:[(1,9)]
    サンプル2:
    入力:(3,4)into[(1,2),(5,9)]出力:[(1,2),(3,4),(5,9)]
    /**
     * Definition of Interval:
     * public classs Interval {
     * int start, end;
     * Interval(int start, int end) {
     * this.start = start;
     * this.end = end;
     * }
     * }
     */
    
    public class Solution {
         
    	/**
    	 * @param intervals:   Sorted interval list.
    	 * @param newInterval: new interval.
    	 * @return: A new interval list.
    	 */
    	public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
         
    		// write your code here
    		List<Interval> ret      = new ArrayList<>();
    		boolean        inserted = false;
    		for (int i = 0; i < intervals.size(); i++) {
         
    			Interval interval = intervals.get(i);
    			if (inserted) {
         
    				ret.add(interval);
    			} else {
         
    				if (newInterval.end < interval.start) {
         
    					ret.add(newInterval);
    					ret.add(interval);
    					inserted = true;
    				} else if (newInterval.start <= interval.end) {
         
    					int start = Math.min(newInterval.start, interval.start);
    					while (i + 1 < intervals.size()
    							&& newInterval.end > interval.end) {
         
    						interval = intervals.get(++i);
    					}
    					if (newInterval.end >= interval.start) {
         
    						ret.add(new Interval(start, Math.max(newInterval.end, interval.end)));
    					} else {
         
    						ret.add(new Interval(start, newInterval.end));
    						ret.add(interval);
    					}
    					inserted = true;
    				} else {
         
    					ret.add(interval);
    				}
    			}
    		}
    		if (!inserted) {
         
    			ret.add(newInterval);
    		}
    		return ret;
    	}
    }
    

    原題リンクはこちら
    に感謝
    この文章を読むのに時間を費やしてくれてありがとう.本人のレベルは限られているので、何か間違っているところがあれば、指摘してください.皆さん、コメント討論を歓迎します.皆さんが毎日少し進歩することを望んでいます.