/* Problem:
 * https://leetcode.com/problems/non-overlapping-intervals/
 */

#include <algorithm>
#include <iostream>
#include <list>
#include <vector>

struct interval {
  int start;
  int end;
};

std::ostream &operator<<(std::ostream &out, const interval i) {
  out << "start: " << i.start << " end: " << i.end << "\n";
  return out;
}

int solution(std::vector<std::vector<int>> &&input) {
  std::sort(input.begin(), input.end());
  std::list<interval> intervals;
  for (auto i : input)
    intervals.push_back({i[0], i[1]});

  int deletions = 0;
  auto left = intervals.begin();
  std::list<interval>::iterator right = left;
  right++;
  while (right != intervals.end()) {
    if (left->end > right->start) {
      deletions++;
      if (left->end <= right->end) {
        intervals.erase(right);
        right = left;
        right++;
      } else {
        intervals.erase(left);
        left = right;
        right++;
      }
    } else {
      left++;
      right++;
    }
  }
  return deletions;
}

int main() {
  std::cout << solution({{1, 2}, {2, 3}, {3, 4}, {1, 3}}) << '\n'
            << solution({{1, 2}, {1, 2}, {1, 2}}) << '\n'
            << solution({{1, 2}, {2, 3}}) << '\n';
  return 0;
}