Algorithm (Greedy)

Let $\mathcal{I}$ be the set of intervals. First, we observe the following fact:

Lemma. Let $\mathcal{I}_{\text{trimmed}}\subset\mathcal{I}$ be the trimmed set of intervals where for any chain of intervals $I_{1}\subset I_{2}\subset…\subset I_{n}$, only $I_{1}$ is retained and the rest are thrown out. Then $\mathrm{OPT}(\mathcal{I})=\mathrm{OPT}(\mathcal{I}_{\text{trimmed}}).$

Proof. We prove this claim by showing that $\mathrm{OPT}(\mathcal{I})\geq\mathrm{OPT}(\mathcal{I}_{\text{trimmed}})$ and $\mathrm{OPT}(\mathcal{I})\leq\mathrm{OPT}(\mathcal{I}_{\text{trimmed}}).$ Note that by construction the first inequality holds since for any $I\in\mathcal{I}_{\text{trimmed}},$ $I\in\mathcal{I}$. For the reverse inequality, suppose there exists $I_{1},I_{2}$ in $\mathcal{I}$ such taht $I_{1}\subset I_{2}$ and there exists $x_{1},x_{2},x_{3},x_{4}$ in the set $S$ that is associated with $\mathrm{OPT}(\mathcal{I})$ and $x_{1},x_{2}\in I_{1},$ $x_{3},x_{4}\in I_{2}\backslash I_{1}.$ Now if there doesn’t exists any interval $I$ such that $I_{1}\not\subseteq I$ and at least one of $x_{3},x_{4}$ is contained in $I$, then $S$ is not a optimum set because $S\backslash\{x_{3},x_{4}\}$ satisfies the condition and has a smaller cardinality (the argument could be used twice to get rid of both $x_{3}$ and $x_{4}$, we leave the details).

Therefore, the set associated with $\mathrm{OPT}(\mathcal{I})$ also consitutes a solution set for $\mathrm{OPT}(\mathcal{I}_{\text{trimmed}})$ and therefore $\mathrm{OPT}(\mathcal{I})\leq\mathrm{OPT}(\mathcal{I}_{\text{trimmed}})$ by minimality of $\mathrm{OPT}(\mathcal{I}_{\mathrm{trimmed}}).$

With this lemma in mind, it suffices for us to find the solution for $\mathcal{I}_{\text{trimmed}}.$ Now denote the minimum intersection set of input intervals $\mathcal{I}$ as $S(\mathcal{I})$. Then we note that $S(\mathcal{I})=S(\pi(\mathcal{I}))$ for any permutation $\pi$. This could be easily verified. Now we construct our solution set $S_{0}(\mathcal{I}_{\text{trimmed}})$ as follows

• Sort all $I\in\mathcal{I}$ by the end points in ascending order(if two end points are the same, sort the starting points by descending order, this makes trimming step easier). And then trim $\mathcal{I}$ as we mentioned before. Denote the sorted and trimmed interval as $\mathcal{I}_{p}.$

• Put the last two end points of the first interval in $\mathcal{I}_{p}$ in $S.$ Then we keep track of the last two largest points, $i_{1},i_{2},$ with $i_{1}\leq i_{2}$, inserted in $S$, and compare with all intervals $I$ in $\mathcal{I}_{p}[1:n]$ in sorted order.

  • If $i_{1},i_{2}\in\mathcal{I}_{p}[i],$ then we move on to $\mathcal{I}_{p}[i+1]$ without adding any new points to $S$.
  • If $i_{1}\notin\mathcal{I}_{p}[i]$ and $i_{2}\in\mathcal{I}_{p}[i],$ then we add the end point of $\mathcal{I}_{p}[i]$ to $S$ and update $i_{1}=i_{2}$ and $i_{2}=\text{end point of }\mathcal{I}_{p}[i]$.
  • If $i_{1},i_{2}\notin\mathcal{I}_{p}[i],$ then we add the last two integral end points of $\mathcal{I}_{p}[i]$ to $S$ and update them to be $i_{1}$ and $i_{2}.$

We claim that this is indeed a optimal intersection set using an exchange argument.

Lemma. Let $S_{\mathrm{OPT}}(\mathcal{I}_{\mathrm{trimmed}})$ be any optimal intersection set. Then $|S_{\mathrm{OPT}}(\mathcal{I}_{\text{trimmed}})|=|S_{0}(\mathcal{I}_{\text{trimmed}})|$.

Proof. For any $i_{1}\leq i_{2}\in I\in S_{\mathrm{OPT}}(\mathcal{I}_{\text{trimmed}})$ and $j_{1}\leq j_{2}\in I\in S_{0}(\mathcal{I}_{\text{trimmed}})$ we could swap $i$’s and $j$’s the result could only be smaller because $j_{1},j_{2}$ is in $I$ and is more likely to be in other overlapping intervals as well by construction (one could formalize this argument by case analysis, we skip it for now).

Code

template <class F>
struct recursive {
  F f;
  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts)  const { return f(std::ref(*this), std::forward<Ts>(ts)...); }

  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts)  { return f(std::ref(*this), std::forward<Ts>(ts)...); }
};

template <class F> recursive(F) -> recursive<F>;
auto const rec = [](auto f){ return recursive{std::move(f)}; };


template<class F, class... Gs> auto compose(F &&f, Gs &&... gs) {
  return [f, gs...](auto &&...args) {
    return f(gs(std::forward<decltype(args)>(args)...)...);
  };
}


class Solution {
 public:
  int intersectionSizeTwo(vector<vector<int>>& intervals) {
    const auto N = size(intervals);

    auto make_sorted = [&](vector<vector<int>> x) {
      std::sort(begin(x), end(x), [&](const auto& a, const auto& b) {
        if (a[1] == b[1])
          return a[0] > b[0];
        else
          return a[1] < b[1];
      });
      return x;
    };

    auto make_trimmed = [&](vector<vector<int>> x) {
      auto acc = vector<vector<int>>{};
      auto go = rec([&](auto &&go, int i, int start, int end) -> void {
        if (i == N)
          return;
        else {
          const auto [cur_start, cur_end] = tuple(x[i][0], x[i][1]);
          if (i == 0) {
            acc.push_back(x[i]);
            go(i + 1, cur_start, cur_end);
          }
          else if (cur_start <= start and end <= cur_end) 
            go(i + 1, start, end);
          else {
            acc.push_back(x[i]);
            go(i + 1, cur_start, cur_end);
          }
        }
      });
      return (go(0, x[0][0], x[0][1]), acc);
    };

    const auto solution = [&](int acc = 0) {
      const auto I = compose(make_trimmed, make_sorted)(intervals);
      const auto N = size(I);
      auto go = rec([&](auto &&go, int i, int start, int end) {
        if (i == N)
          return;
        else {
          const auto [cur_start, cur_end] = tuple(I[i][0], I[i][1]);
          if (i == 0 or i > 0 and end < cur_start) {
            acc += 2;
            go(i + 1, cur_end - 1, cur_end);
          }
          else if (i > 0 and start < cur_start and end >= cur_start and end <= cur_end) {
            acc += 1;
            go(i + 1, end, cur_end);
          }
          else if (i > 0 and start >= cur_start and end >= cur_start and end <= cur_end) 
            go(i + 1, start, end);
          else
            throw std::domain_error("unmatched case");
        }
      });
      return (go(0, I[0][0], I[0][1]), acc);
    }();

    return solution;
  }
};