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

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Link: View error logs on GitHub Actions

Operations

• interval_scheduling_k(l[N], r[N], k)
  • N個の半開区間[l[i], r[i])を、ある点で最大k個までの重複を許して選ぶときに、選べる個数を最大化する方法を返す。
  • Time complexity $O(N \log N)$

Requirements

Notes

Problems

• yukicoder No.580 旅館の予約計画
• Codeforces Round #595 (Div. 3) D2. Too Many Segments (hard version)

References

• http://buyoh.hateblo.jp/entry/2017/10/25/160236

Verified with

• test/yukicoder/580/main.test.cpp

Code

#pragma once
#include <algorithm>
#include <iterator>
#include <numeric>
#include <set>
#include <utility>
#include <vector>

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 2 "Mylib/Typical/interval_scheduling_k.cpp"
#include <algorithm>
#include <iterator>
#include <numeric>
#include <set>
#include <utility>
#include <vector>

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

Back to top page