data-structure/interval-scheduling.hpp

View this file on GitHub
Last update: 2023-07-08 14:12:19+09:00
Include: #include "data-structure/interval-scheduling.hpp"
Link: https://atcoder.jp/contests/keyence2020/tasks/keyence2020_b

Depends on

data-structure/base.hpp

Code

#pragma once

#include "./base.hpp"

#include <vector>

namespace matumoto {
  // verify:https://atcoder.jp/contests/keyence2020/tasks/keyence2020_b
  template <typename T>
  class IntervalScheduling {
    vector<pair<T, T>> intervals_;
    vector<bool> used;

  public:
    IntervalScheduling() {}

    void add_interval(T l, T r) {
      intervals_.emplace_back(l, r);
    }

    int inf() {
      return numeric_limits<int>::max() / 2;
    }

    void build() {
      used.assign(intervals_.size(), false);

      sort(intervals_.begin(), intervals_.end(), [](pair<T, T> a, pair<T, T> b) {
        if (a.second != b.second)
          return a.second < b.second;
        return a.first < b.first;
      });

      int last = -inf();
      for (size_t i = 0; i < intervals_.size(); i++) {
        auto [l, r] = intervals_[i];

        if (last <= l) {
          used[i] = true;
          last = r;
        }
      }
    }

    bool is_used(int k) {
      return used[k];
    }

    vector<pair<T, T>> intervals() {
      vector<pair<T, T>> res;
      for (size_t i = 0; i < intervals_.size(); i++) {
        if (!used[i])
          continue;
        res.emplace_back(intervals_[i]);
      }
      return res;
    }
  };
} // namespace matumoto

#line 2 "data-structure/interval-scheduling.hpp"

#line 2 "data-structure/base.hpp"

namespace matumoto {
  using namespace std;
}
#line 4 "data-structure/interval-scheduling.hpp"

#include <vector>

namespace matumoto {
  // verify:https://atcoder.jp/contests/keyence2020/tasks/keyence2020_b
  template <typename T>
  class IntervalScheduling {
    vector<pair<T, T>> intervals_;
    vector<bool> used;

  public:
    IntervalScheduling() {}

    void add_interval(T l, T r) {
      intervals_.emplace_back(l, r);
    }

    int inf() {
      return numeric_limits<int>::max() / 2;
    }

    void build() {
      used.assign(intervals_.size(), false);

      sort(intervals_.begin(), intervals_.end(), [](pair<T, T> a, pair<T, T> b) {
        if (a.second != b.second)
          return a.second < b.second;
        return a.first < b.first;
      });

      int last = -inf();
      for (size_t i = 0; i < intervals_.size(); i++) {
        auto [l, r] = intervals_[i];

        if (last <= l) {
          used[i] = true;
          last = r;
        }
      }
    }

    bool is_used(int k) {
      return used[k];
    }

    vector<pair<T, T>> intervals() {
      vector<pair<T, T>> res;
      for (size_t i = 0; i < intervals_.size(); i++) {
        if (!used[i])
          continue;
        res.emplace_back(intervals_[i]);
      }
      return res;
    }
  };
} // namespace matumoto