一裙戏、題目435. 無重疊區(qū)間
LeetCode地址：https://leetcode-cn.com/problems/non-overlapping-intervals/
難度：中等
給定一個(gè)區(qū)間的集合卿堂，找到需要移除區(qū)間的最小數(shù)量，使剩余區(qū)間互不重疊。
注意:
可以認(rèn)為區(qū)間的終點(diǎn)總是大于它的起點(diǎn)箍铲。
區(qū)間 [1,2] 和 [2,3] 的邊界相互“接觸”冻押，但沒有相互重疊。
示例 1:
輸入: [ [1,2], [2,3], [3,4], [1,3] ]
輸出: 1
解釋: 移除 [1,3] 后鳞陨，剩下的區(qū)間沒有重疊昨寞。
示例 2:
輸入: [ [1,2], [1,2], [1,2] ]
輸出: 2
解釋: 你需要移除兩個(gè) [1,2] 來使剩下的區(qū)間沒有重疊。
示例 3:
輸入: [ [1,2], [2,3] ]
輸出: 0
解釋: 你不需要移除任何區(qū)間厦滤，因?yàn)樗鼈円呀?jīng)是無重疊的了援岩。
二、解題思路
先把區(qū)間按照結(jié)尾的大小進(jìn)行升序排序掏导，找到數(shù)組end中的最小值享怀。用end值與數(shù)組start相互比較，保留符合的區(qū)間趟咆。按照這個(gè)策略比較添瓷，找到符合的區(qū)間。
三值纱、實(shí)現(xiàn)過程
c++
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if (intervals.empty()) {
return 0;
}
int n = intervals.size();
sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b){
return a[1] < b[1];
});
int total = 0, prev = intervals[0][1];
for (int i = 1; i < n; ++i) {
if (intervals[i][0] < prev) {
++total;
} else {
prev = intervals[i][1];
}
}
return total;
}
};
PHP方法一
class Solution {
/**
* @param Integer[][] $intervals
* @return Integer
*/
function eraseOverlapIntervals($intervals) {
//處理簡(jiǎn)單情況
$len = count($intervals);
if($len < 2){
return 0;
}
//按照區(qū)間開始位置升序排列
for($i = 0; $i < $len - 1 ;$i++){
for($j = $i + 1;$j < $len;$j++){
if($intervals[$i][1] > $intervals[$j][1]){
$temp = $intervals[$i];
$intervals[$i] = $intervals[$j];
$intervals[$j] = $temp;
}
}
}
//計(jì)算法結(jié)果
$total = 0;
$prev = $intervals[0][1];
for($i = 1; $i < $len;$i++){
if($prev > $intervals[$i][0]){
++$total;
}else{
$prev = $intervals[$i][1];
}
}
return $total;
}
}
PHP方法二
class Solution {
/**
* @param Integer[][] $intervals
* @return Integer
*/
function eraseOverlapIntervals($intervals) {
array_multisort($intervals);
$w = array_column($intervals,0);
$h = array_column($intervals,1);
$end = $h[0];
$len = count($w);
for($i=1;$i<$len;$i++){
if($w[$i]<$end){
unset($w[$i]);
}else{
$end = min(array_slice($h,$i));
}
}
$count = count($h)-count($w);
return $count;
}
}
PS:方法二來自網(wǎng)友的解法鳞贷，那么問題來了兩種方法差距為什么這么大?尤其方法一居然比js慢那么多。虐唠。搀愧。
JavaScript
/**
* @param {number[][]} intervals
* @return {number}
*/
var eraseOverlapIntervals = function(intervals) {
var len = intervals.length;
if(len < 2){
return 0;
}
for(var i = 0; i < len - 1 ;i++){
for(var j = i + 1;j < len;j++){
if(intervals[i][1] > intervals[j][1]){
temp = intervals[i];
intervals[i] = intervals[j];
intervals[j] = temp;
}
}
}
var total = 0;
var prev = intervals[0][1];
for(var i = 1; i < len;i++){
if(prev > intervals[i][0]){
++total;
}else{
prev = intervals[i][1];
}
}
return total;
};
三、小結(jié)
同樣的算法疆偿，php與js的差距我不得不懷疑php對(duì)二維數(shù)組的支持真的不太友好妈橄。
Javascript排序可通“intervals.sort((a,b)=>a[1] - b[1]);”直接實(shí)現(xiàn)，那么php有沒有什么好的方法翁脆？
