misc/segment_union.hpp

• View this file on GitHub
• Last update: 2023-08-02 22:18:29+07:00
• Include: #include "misc/segment_union.hpp"

Code

auto segment_union = [](vector<pair<int, int>> &segs) {
  sort(segs.begin(), segs.end());
  vector<pair<int, int>> res, lr;
  for (auto &[u, v] : segs) {
    lr.emplace_back(u, 0);
    lr.emplace_back(v + 1, 1);
  }
  stack<int> st;
  sort(lr.begin(), lr.end());
  for (auto &[x, t] : lr) {
    if (t == 0) {
      st.push(x);
    } else {
      if (st.size() == 1) {
        res.emplace_back(st.top(), x - 1);
      }
      st.pop();
    }
  }
  return res;
};

#line 1 "misc/segment_union.hpp"
auto segment_union = [](vector<pair<int, int>> &segs) {
  sort(segs.begin(), segs.end());
  vector<pair<int, int>> res, lr;
  for (auto &[u, v] : segs) {
    lr.emplace_back(u, 0);
    lr.emplace_back(v + 1, 1);
  }
  stack<int> st;
  sort(lr.begin(), lr.end());
  for (auto &[x, t] : lr) {
    if (t == 0) {
      st.push(x);
    } else {
      if (st.size() == 1) {
        res.emplace_back(st.top(), x - 1);
      }
      st.pop();
    }
  }
  return res;
};

Back to top page