ネクタイの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)]
原題リンクはこちら
に感謝
この文章を読むのに時間を費やしてくれてありがとう.本人のレベルは限られているので、何か間違っているところがあれば、指摘してください.皆さん、コメント討論を歓迎します.皆さんが毎日少し進歩することを望んでいます.
目次
重複のない区間開始端点に従ってソートされた区間リストを与えます.
リストに新しい区間を挿入し、リスト内の区間が秩序正しく重複していないことを確認します(必要に応じて区間をマージできます).
サンプル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;
}
}
原題リンクはこちら
に感謝
この文章を読むのに時間を費やしてくれてありがとう.本人のレベルは限られているので、何か間違っているところがあれば、指摘してください.皆さん、コメント討論を歓迎します.皆さんが毎日少し進歩することを望んでいます.