Interval scheduling problem
(Mylib/Typical/interval_scheduling.cpp)

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

Operations

• interval_scheduling(l[N], r[N])
  • N個の半開区間[l[i], r[i])を互いに交差しないように選べる個数を最大にする方法。
  • Time complexity $O(N \log N)$

Requirements

Notes

Problems

• KUPC 2015 A - 東京都
• Codeforces Round #296 (Div. 1) B. Clique Problem

References

Verified with

• test/aoj/ALDS1_15_C/main.test.cpp

Code

#pragma once
#include <algorithm>
#include <limits>
#include <numeric>
#include <utility>
#include <vector>

namespace haar_lib {
  template <typename T>
  std::vector<std::pair<T, T>> interval_scheduling(const std::vector<T> &l, const std::vector<T> &r) {
    const int N = l.size();
    std::vector<std::pair<T, T>> ret;
    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]; });

    auto b = std::numeric_limits<T>::lowest();

    for (int i : ord) {
      if (l[i] >= b) {
        ret.emplace_back(l[i], r[i]);
        b = r[i];
      }
    }

    return ret;
  }
}  // namespace haar_lib

#line 2 "Mylib/Typical/interval_scheduling.cpp"
#include <algorithm>
#include <limits>
#include <numeric>
#include <utility>
#include <vector>

namespace haar_lib {
  template <typename T>
  std::vector<std::pair<T, T>> interval_scheduling(const std::vector<T> &l, const std::vector<T> &r) {
    const int N = l.size();
    std::vector<std::pair<T, T>> ret;
    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]; });

    auto b = std::numeric_limits<T>::lowest();

    for (int i : ord) {
      if (l[i] >= b) {
        ret.emplace_back(l[i], r[i]);
        b = r[i];
      }
    }

    return ret;
  }
}  // namespace haar_lib

Back to top page