thảo luận Leetcode mỗi ngày

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int ans = 0, l = 0;
        // l ở đây có thể hiểu như index của interval tạm thời cuối cùng
        // mà không bị xóa
        sort(intervals.begin(),intervals.end());
        // sort theo tăng dần của start
        for (int i = 1; i < intervals.size(); i++){
            if (intervals[l][1] <= intervals[i][0]){
                l = i;
                // trường hợp end_l <= start_i thì không cần phải xóa gì cả
            } else{
                ans++;
                if (intervals[l][1] > intervals[i][1]) l = i;
                // trường hợp này cần lưu ý nếu như end_l > end_i thì ta nên xóa l
                // và lúc này chọn i làm l mới
            }
        }
        return ans;
    }
};

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals = sorted(intervals, key=lambda x:x[1])
        result = 0
        previous_end = -inf

        for start, end in intervals:
            if start >= previous_end:
                previous_end = end
            else:
                result += 1
        
        return result

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals = sorted(intervals, key = lambda x:x[1])
        last = -123456789
        ans = 0
        for x, y in intervals:
            if last > x: ans += 1
            else: last = y
        return ans

var eraseOverlapIntervals = function(intervals) {
  intervals.sort((u, v) => u[1] - v[1]);
  let lastEnd = -Infinity, ans = intervals.length;

  for (const [start, end] of intervals) {
    if (lastEnd <= start) {
      lastEnd = end;
      ans--;
    }
  }
  
  return ans;
};

impl Solution {
    pub fn erase_overlap_intervals(mut intervals: Vec<Vec<i32>>) -> i32 {
        intervals.sort_by_key(|x| x[1]);
        let (mut res, mut last_end) = (0, intervals[0][1]);
        for interval in intervals[1..].iter() {
            if last_end > interval[0] {
                res += 1;
            } else {
                last_end = interval[1];
            }
        }
        res
    }
}

struct Data
{
    Data() = default;
    Data(int s, int e) : start{s}, end{e}
    {}
    int start{};
    int end{};
};

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        std::vector<Data> lst;
        for (const auto& v : intervals)
        {
            lst.emplace_back(v[0], v[1]);
        }

        std::sort(lst.begin(), lst.end(), [](Data& lhs, Data& rhs){return lhs.end < rhs.end;});
        int count{};
        int cur_end = lst[0].start;

        int result = intervals.size();

        for (const auto& d : lst)
        {
            if (d.start >= cur_end)
            {
                result--;
                cur_end = d.end;
            }
        }

        return result;
    }
};

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        n = len(intervals)
        intervals = sorted(intervals, key=lambda x:x[1])
        ends = [end for start, end in intervals]
        dp = [1 for interval in intervals]
        
        for current_index in range(1, n):
            start, end = intervals[current_index]
            previous_index = bisect_right(ends, start, 0, current_index) - 1
            
            if previous_index >= 0:
                dp[current_index] += dp[previous_index]
                
            dp[current_index] = max(dp[current_index], dp[current_index - 1])

        return n - dp[-1]

var eraseOverlapIntervals = function(intervals) {
  const stack = [];
  intervals = _.sortBy(intervals, '1');

  for (const [start, end] of intervals) {
    if (!stack.length || stack[stack.length-1] <= start) {
      stack.push(end);
    }
  }

  return intervals.length - stack.length;
};

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        result = []
        stack = []

        for asteroid in asteroids:
            if asteroid > 0:
                stack.append(asteroid)
                continue
            
            while len(stack) > 0 and stack[-1] < abs(asteroid):
                stack.pop()

            if len(stack) == 0:
                result.append(asteroid)
                continue
            
            if stack[-1] == abs(asteroid):
                stack.pop()

        result += stack
        return result

function asteroidCollision(asteroids: number[]): number[] {
    let stack = [asteroids[0]];
    for (let i = 1; i < asteroids.length; i++) {
        if (stack.length === 0) {
            stack.push(asteroids[i])
        } else if (stack[stack.length - 1] * asteroids[i] > 0 || stack[stack.length - 1] < 0) {
            stack.push(asteroids[i])
        } else {
            if (Math.abs(asteroids[i]) > Math.abs(stack[stack.length - 1])) {
                stack.pop()
                i--;
            } else if (Math.abs(asteroids[i]) === Math.abs(stack[stack.length - 1])) {
                stack.pop()
            }
        }
    }
    return stack
};