test/yukicoder/580/main.test.cpp

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Problem: https://yukicoder.me/problems/no/580
• Link: View error logs on GitHub Actions

Depends on

• Interval scheduling problem (Allow no more than k intervals to overlap) (Mylib/Typical/interval_scheduling_k.cpp)

Code

#define PROBLEM "https://yukicoder.me/problems/no/580"

#include <iostream>
#include <vector>
#include "Mylib/Typical/interval_scheduling_k.cpp"

namespace hl = haar_lib;

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  int n, m;
  std::cin >> n >> m;

  std::vector<int> l(m), r(m);

  for (int i = 0; i < m; ++i) {
    int d;
    std::cin >> d;
    int h1, m1;
    std::cin >> h1;
    std::cin.ignore();
    std::cin >> m1;

    int o;
    std::cin >> o;
    int h2, m2;
    std::cin >> h2;
    std::cin.ignore();
    std::cin >> m2;

    l[i] = d * 24 * 60 + h1 * 60 + m1;
    r[i] = o * 24 * 60 + h2 * 60 + m2 + 1;
  }

  auto res = hl::interval_scheduling_k(l, r, n);
  std::cout << res.size() << "\n";

  return 0;
}

#line 1 "test/yukicoder/580/main.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/580"

#include <iostream>
#include <vector>
#line 2 "Mylib/Typical/interval_scheduling_k.cpp"
#include <algorithm>
#include <iterator>
#include <numeric>
#include <set>
#include <utility>
#line 8 "Mylib/Typical/interval_scheduling_k.cpp"

namespace haar_lib {
  auto interval_scheduling_k(std::vector<int> l, std::vector<int> r, int k) {
    const int N = l.size();

    std::vector<int> ord(N);
    std::iota(ord.begin(), ord.end(), 0);
    std::sort(ord.begin(), ord.end(), [&](int i, int j) { return r[i] < r[j]; });

    std::multiset<int> a;
    std::vector<std::pair<int, int>> ret;

    for (int i : ord) {
      auto it = a.upper_bound(l[i]);

      if (it != a.begin()) {
        it = std::prev(it);
        a.erase(it);
      }

      if ((int) a.size() < k) {
        a.insert(r[i]);
        ret.emplace_back(l[i], r[i]);
      }
    }

    return ret;
  }
}  // namespace haar_lib
#line 6 "test/yukicoder/580/main.test.cpp"

namespace hl = haar_lib;

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  int n, m;
  std::cin >> n >> m;

  std::vector<int> l(m), r(m);

  for (int i = 0; i < m; ++i) {
    int d;
    std::cin >> d;
    int h1, m1;
    std::cin >> h1;
    std::cin.ignore();
    std::cin >> m1;

    int o;
    std::cin >> o;
    int h2, m2;
    std::cin >> h2;
    std::cin.ignore();
    std::cin >> m2;

    l[i] = d * 24 * 60 + h1 * 60 + m1;
    r[i] = o * 24 * 60 + h2 * 60 + m2 + 1;
  }

  auto res = hl::interval_scheduling_k(l, r, n);
  std::cout << res.size() << "\n";

  return 0;
}

Back to top page