中金員工人均月薪降至3.5萬元，四年時間累計下滑65%。。

最近中金一名員工的離世引起網路的極大關註， 除此之外大家最關註的就是中金員工的收入，據「每日經濟新聞 」中金員工的收入從4年前的月薪10萬降到現在的月薪3.5萬，降幅達到65%。

我們在網上經常看到程式設計師曬收入，曬offer，曬工牌，但很少看到搞金融的曬這曬那， 果然最富的是他們，最低調的還是他們。

從月薪10萬降到月薪3.5萬，這種降薪振幅確實有點大，不過我覺得就算月薪3.5萬也算是高薪了，可能我沒有拿過月薪10萬的收入，對他這種情況也理解不了。

--------------下面是今天的演算法題--------------

來看下今天的演算法題，這題是LeetCode的第57題：插入區間。

問題描述

來源：LeetCode第57題

難度：中等

給你一個無重疊的， 按照區間起始端點排序的區間 列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 個區間的開始和結束，並且 intervals 按照 starti 升序排列。同樣給定一個區間 newInterval = [start, end] 表示另一個區間的開始和結束。

在 intervals 中插入區間 newInterval，使得 intervals 依然按照 starti 升序排列，且區間之間不重疊（如果有必要的話，可以合並區間）。返回插入之後的 intervals。

範例1：

輸入 ：intervals = [[1,3],[6,9]], newInterval = [2,5]

輸出 ：[[1,5],[6,9]]

範例2：

輸入 ：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]

輸出 ：[[1,2],[3,10],[12,16]]

解釋 ：這是因為新的區間 [4,8] 與 [3,5],[6,7],[8,10] 重疊。

問題分析

這題說的是原來的區間是按照起始點排序的，且區間沒有重疊。讓我們在原來的區間插入一個新的區間，如果有重疊就把他們合並，如下圖所示，因為區間[1,3]和區間[2,5]有重疊，

這裏要判斷要合並的區間和上面的哪些區間有重疊，因為上面的區間都已經按照起始點排序了，如果 當前區間的終點小於合並區間的起始點， 他們是沒有重疊的 ，或者 當前區間的起始點大於合並區間的終點 ，他們也是沒有重疊的。

沒有重疊的區間只需要單獨保存下來，有重疊的區間需要合並。

JAVA：

publicint[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> ans = new ArrayList<>();
for (int[] interval : intervals) {
if (newInterval == null || interval[1] < newInterval[0]) {
// 前面單獨的添加進來，或者已經合並完了，把後面的添加進來
ans.add(interval);
} elseif (interval[0] > newInterval[1]) {
ans.add(newInterval);// 後面單獨的區間。
ans.add(interval);
newInterval = null;
} else {// 合並區間
newInterval[0] = Math.min(newInterval[0], interval[0]);
newInterval[1] = Math.max(newInterval[1], interval[1]);
}
}
// 如果合並之後的區間沒有保存下來，要保存下來
if (newInterval != null)
ans.add(newInterval);
return ans.toArray(newint[ans.size()][]);
}


C++：

public:
vector<vector<int>> insert(vector<vector<int>> &intervals, vector<int> &newInterval){
vector<vector<int>> res;
bool finish = false;// 合並完了，後面的不需要再合並了，直接添加
for (autoconst &interval: intervals) {
if (finish || interval[1] < newInterval[0]) {
res.emplace_back(interval);// 前面單獨
} elseif (interval[0] > newInterval[1]) {// 後面單獨
res.emplace_back(newInterval);
res.emplace_back(interval);
finish = true;
} else {// 有交叉，合並
newInterval[0] = min(newInterval[0], interval[0]);//get min
newInterval[1] = max(newInterval[1], interval[1]);//get max
}
}
if (!finish)
res.emplace_back(newInterval);
return res;
}


Python：

definsert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
ans = []
for interval in intervals:
ifnot newInterval or interval[1] < newInterval[0]:
# 前面單獨的添加進來，或者已經合並完了，把後面的添加進來
ans.append(interval)
elif interval[0] > newInterval[1]:
ans.append(newInterval[:]) # 後面單獨的區間。
ans.append(interval)
newInterval.clear()
else: # 合並區間
newInterval[0] = min(newInterval[0], interval[0])
newInterval[1] = max(newInterval[1], interval[1])
# 如果合並之後的區間沒有保存下來，要保存下來
if newInterval:
ans.append(newInterval)
return ans


IT交流群

組建了程式設計師，架構師，IT從業者交流群，以 交流技術 、 職位內推 、 行業探討 為主