牛客NC222 插入区间【中等数组，区间合并问题 Java/Go/PHP/C++】lintcode30 插入区间

题目

在这里插入图片描述
题目链接：
https://www.nowcoder.com/practice/1d784b5472ab4dde88ea2331d16ee909
https://www.lintcode.com/problem/30/solution/56586

思路

在这里插入图片描述

Java代码

import java.util.*;

/*
 * public class Interval {
 *   int start;
 *   int end;
 *   public Interval(int start, int end) {
 *     this.start = start;
 *     this.end = end;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param Intervals Interval类一维数组 
     * @param newInterval Interval类 
     * @return Interval类一维数组
     */
    public Interval[] insertInterval (Interval[] arr, Interval obj) {
        //这种题，直接看答案，梳理思路就行，多练就会了
            //https://blog.csdn.net/bao_14440/article/details/132548294
          int i=0;
          List<Interval> merged = new ArrayList<>();
          //添加区间最大值小于newInterval的开始位置
            while (i<arr.length && arr[i].end<obj.start ){
                merged.add(arr[i]);
                i++;
            }

            //合并区间
            while (i<arr.length && arr[i].start <=obj.end){
                obj.start=Math.min(arr[i].start,obj.start);
                obj.end = Math.max(arr[i].end,obj.end);
                i++;
            }

            merged.add(obj);
            //添加剩下的区间到merged列表中
            while (i<arr.length){
                merged.add(arr[i]);
                i++;
            }

            return merged.toArray(new Interval[merged.size()]);
    }
}

Go代码

package main

import . "nc_tools"

/*
 * type Interval struct {
 *   Start int
 *   End int
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param Intervals Interval类一维数组
 * @param newInterval Interval类
 * @return Interval类一维数组
 */
func insertInterval(Intervals []*Interval, newInterval *Interval) []*Interval {
	//这种题，直接看答案，梳理思路就行，多练就会了
	//https://blog.csdn.net/bao_14440/article/details/132548294
	merged := []*Interval{}

	idx := 0

	//找到插入区间的起始位置，最大值要小于newInterval的开始位置
	for idx < len(Intervals) && Intervals[idx].End < newInterval.Start {
		merged = append(merged, Intervals[idx])
		idx++
	}

	//合并区间
	for idx < len(Intervals) && Intervals[idx].Start <= newInterval.End {
		curstart := newInterval.Start
		curend := newInterval.End
		if Intervals[idx].Start < curstart {
			newInterval.Start = Intervals[idx].Start
		}

		if Intervals[idx].End > curend {
			newInterval.End = Intervals[idx].End
		}

		idx++
	}

	merged = append(merged, newInterval)
	//继续添加后面的区间
	for idx < len(Intervals) {
		merged = append(merged, Intervals[idx])
		idx++
	}

	return merged
}

PHP代码

<?php

/*class Interval{
    var $start = 0;
    var $end = 0;
    function __construct($a, $b){
        $this->start = $a;
        $this->end = $b;
    }
}*/

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param Intervals Interval类一维数组 
 * @param newInterval Interval类 
 * @return Interval类一维数组
 */
function insertInterval( $Intervals ,  $newInterval )
{
    //这种题，直接看答案，梳理思路就行，多练就会了
    //https://blog.csdn.net/bao_14440/article/details/132548294
    $merged = [];

    $idx =0;
    //找到插入位置起点，起点前面的最大值要小于$newInterval的start
    while ($idx < count($Intervals) && $Intervals[$idx]->end < $newInterval->start) {
        $merged[count($merged)] = $Intervals[$idx];
        $idx++;
    }

    //合并区间
    while ($idx<count($Intervals) && $Intervals[$idx]->start <= $newInterval->end){
        $curstart = $newInterval->start;
        $curend = $newInterval->end;

        if($curstart > $Intervals[$idx]->start){
            $newInterval->start = $Intervals[$idx]->start;
        }

        if($curend < $Intervals[$idx]->end){
            $newInterval->end = $Intervals[$idx]->end;
        }
        $idx++;
    }

    $merged[count($merged)] = $newInterval;

    //继续添加剩下的区间到结果中
    while ($idx<count($Intervals)){
        $merged[count($merged)] = $Intervals[$idx];
        $idx++;
    }
    

    return $merged;
}

C++代码

/**
 * struct Interval {
 *  int start;
 *  int end;
 *  Interval(int s, int e) : start(start), end(e) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param Intervals Interval类vector
     * @param newInterval Interval类
     * @return Interval类vector
     */
    vector<Interval> insertInterval(vector<Interval>& Intervals,
                                    Interval newInterval) {
        //这种题，直接看答案，梳理思路就行，多练就会了
        //https://blog.csdn.net/bao_14440/article/details/132548294

        vector<Interval> merged;

        int i=0;
        //找到插入区间的位置，最大值要小于newInterval的start
        while (i<Intervals.size()&& Intervals[i].end< newInterval.start){

            merged.push_back(Intervals[i++]);
        }


        //合并区间
        while (i<Intervals.size() && Intervals[i].start<=newInterval.end){

            int curstart = newInterval.start;
            int curend = newInterval.end;

            if(curstart > Intervals[i].start){
                newInterval.start = Intervals[i].start;
            }

            if(curend < Intervals[i].end){
                newInterval.end = Intervals[i].end;
            }

            i++;
        }

        merged.push_back(newInterval);

        //继续添加后面的区间
        while (i<Intervals.size()){

            merged.push_back(Intervals[i++]);
        }

        return merged;
    }
};