C++二分算法：最多可以参加的会议数目 II

template<class _Kty,class _Ty,bool bValueDdes,bool bOutSmallKey> 
class COrderValueMap 
{
public:
  void Add (_Kty iValue, _Ty iNum)
  {
    if (bOutSmallKey)
    {
      if (bValueDdes)
      {
        AddOutSmall(iValue, iNum, std::less_equal<_Ty>(), std::greater_equal<_Ty>());
      }
      else
      {
      }
    }
    else 
    {
      if (bValueDdes)
      {
        AddNotOutSmall(iValue, iNum, std::greater_equal<_Ty>(), std::less_equal<_Ty>());
      }
      else
      {
        AddNotOutSmall(iValue, iNum, std::less_equal<_Ty>(), std::greater_equal<_Ty>());
      }
    }
  };
  template<class _Pr1, class _Pr2>
  void AddOutSmall(_Kty key, _Ty value, _Pr1 pr1, _Pr2 pr2)
  {
    auto it = m_map.lower_bound(key);
    if ((m_map.end() != it) && pr1(it->second, value))
    {
      return;//被旧值淘汰
    }
    auto ij = it;
    while (it != m_map.begin())
    {
      --it;
      if (pr2(it->second, value))
      {
        it = m_map.erase(it);
      }
    }
    m_map[key] = value;
  }
  template<class _Pr1, class _Pr2>
  void AddNotOutSmall(_Kty key, _Ty value, _Pr1 pr1,_Pr2 pr2 )
  {
    auto it = m_map.upper_bound(key);
    if ((m_map.begin() != it) && pr1(std::prev(it)->second, value))
    {
      return;//被淘汰
    }
    auto ij = it;
    for (; (m_map.end() != ij) && pr2(ij->second, value); ++ij);
    m_map.erase(it, ij);
    m_map[key] = value;
  };
  std::map<_Kty, _Ty> m_map;
};
class Solution {
public:
  int maxValue(vector<vector<int>>& events, int k) {
    COrderValueMap<int, int, true, false> mPre;
    for (const auto& v : events)
    {
      mPre.Add(v[1], v[2]);
    }
    while (--k)
    {
      COrderValueMap<int, int, true, false> dp;
      for (const auto& v : events)
      {
        auto it = mPre.m_map.lower_bound(v[0]);
        int iNewValue = v[2];
        if (mPre.m_map.begin() != it)
        {
          iNewValue += std::prev(it)->second;
        }
        dp.Add(v[1], iNewValue);
      }
      dp.m_map.swap(mPre.m_map);
    }
    return mPre.m_map.rbegin()->second;
  } 
};

template <class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
template <class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{
  vector<vector<int>> events;
  int k;
  int res;
  {
    Solution slu;
    events = { {1,2,4},{3,4,3},{2,3,1} };
    k = 2;
    res = slu.maxValue(events, k);
    Assert(res,7 );
  }
  {
    Solution slu;
    events = { {1,2,4},{3,4,3},{2,3,10} };
    k = 2;
    res = slu.maxValue(events, k);
    Assert(res, 10);
  }
  {
    Solution slu;
    events = { {1,1,1},{2,2,2},{3,3,3},{4,4,4} };
    k = 3;
    res = slu.maxValue(events, k);
    Assert(res, 9);
  }
  //CConsole::Out(res);
}