2023-07-19 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's July LeetCoding Challenge with cpp.

July LeetCoding Challenge 19

Description

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.

 

Constraints:

  • 1 <= intervals.length <= 105
  • intervals[i].length == 2
  • -5 * 104 <= starti < endi <= 5 * 104

Solution

auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();
class Solution {
public:
  int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(), [](const vector<int> &a, const vector<int> &b) {
      return a[1] < b[1] ||(a[1] == b[1] && a[0] < b[0]);
    });

    int end = -100000;
    int answer = 0;
    for(const auto &interval : intervals) {
      if(interval[0] < end) {
        answer += 1;
      } else {
        end = interval[1];
      }
    }

    return answer;
  }
};

// Accepted
// 58/58 cases passed (478 ms)
// Your runtime beats 70.68 % of cpp submissions
// Your memory usage beats 99.9 % of cpp submissions (88.8 MB)
Algorithm