Re: [閒聊] 每日LeetCode

[yam276 (史萊哲林的優等生)]

https://leetcode.com/problems/non-overlapping-intervals/submissions/

435. Non-overlapping Intervals

Given an array of intervals intervals where intervals[i] = [starti, endi],
return the minimum number of intervals you need to remove to make the rest of
the intervals non-overlapping.

給一堆區間 要你算刪掉幾個區間會讓他們不重疊


Example 1:
Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1

Explanation: [1,3] can be removed and the rest of the intervals are non-
overlapping.


Example 2:
Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2

Explanation: You need to remove two [1,2] to make the rest of the intervals
non-overlapping.


Example 3:
Input: intervals = [[1,2],[2,3]]
Output: 0

Explanation: You don't need to remove any of the intervals since they're
already non-overlapping.


Step：

0. Vec.len() = 0 判斷

1. 先根據區間尾排列Vec

2. 設result = 1代表不重複區間數，設last_tail來當目前區間的尾

3. 前後區間不重疊(後者head >= 前者tail)則result+1

4. return 區間數減不重複區間數


只算重疊區間也可以 就反過來寫


Code:

impl Solution
{
    pub fn erase_overlap_intervals(intervals: Vec<Vec<i32>>) -> i32
    {
        if intervals.is_empty()
        {
            return 0;
        }

        let mut intervals = intervals;
        intervals.sort_by(|a, b| a[1].cmp(&b[1]));

        let mut result = 1;
        let mut last_tail = intervals[0][1];
        for pair_nums in intervals.iter()
        {
            if(pair_nums[0] >= last_tail)
            {
                last_tail = pair_nums[1];
                result += 1;
            }
        }

        return (intervals.len() - result) as i32;
    }
}


等價於：

class Solution
{
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals)
    {
        if (intervals.size() < 1)
            return 0;

        std::sort(intervals.begin(), intervals.end(),
            [](vector<int>& a, vector<int>& b)
            {
                return a[1] < b[1];
            });

        int result = 0;
        int last_tail = intervals[0][1];
        for (auto& pair_nums : intervals)
        {
            if (pair_nums[0] >= last_tail)
            {
                last_tail = pair_nums[1];
                result++;
            }
        }
        return intervals.size() - result;
    }
};



--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.248.143.163 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1689754805.A.A6C.html
→ Rushia: 大師
推 sustainer123: 大師