Interval scheduling problem in C++

Question

The problem I attempted to solve is described as:

What is the largest subset of mutually non-overlapping intervals which can be selected from I? Where I is a set of N intervals where each interval has the same weight per item within the interval.

I claim the algorithm runs at \$O(N \lg N)\$ and has a space complexity of \$O(N)\$. I would like a review on the algorithm itself and the utility class used to solve the problem. I am interested in suggestions on better data structures others might use, and possible optimizations to the algorithm itself.

The algorithm with a driver (the driver has no error checking) is defined as:

#include <utility/interval.h>

#include <iostream>
#include <list>
#include <sstream>

/// Problem: What is the largest subset of mutually non-overlapping intervals
/// which can be selected form the input of a set of N intervals. Assume that
/// the profit for each interval is the same.
void max_scheduling(std::list<utility::interval<int>> intervals)
{
  intervals.sort();

  std::list<utility::interval<int>> subset;
  while (!intervals.empty()) {
    subset.push_back(intervals.front());
    intervals.pop_front();

    while (subset.back().intersects(intervals.front())) {
      intervals.pop_front();
    }
  }

  for (auto interval : subset) {
    std::cout << interval << std::endl;
  }
}

int main(int argc, char *argv[])
{
  std::string input;
  unsigned int test_cases = 0;

  std::cin >> input;
  std::stringstream ss;
  ss << input;
  ss >> test_cases;

  std::list<utility::interval<int>> intervals;
  for (unsigned int test_case = 0; test_case < test_cases; ++test_case) {
    std::cin >> input;
    ss.clear();
    ss << input;
    int min = 0;
    ss >> min;

    std::cin >> input;
    ss.clear();
    ss << input;
    int max = 0;
    ss >> max;

    intervals.push_back(utility::interval<int>(min, max));
  }

  max_scheduling(intervals);

  return 0;
}

The utility class' declaration and definition are as follows:

// Declaration
#ifndef INTERVAL_H_INCLUDED
#define INTERVAL_H_INCLUDED

#include <utility/declspec.h>

#include <tuple>
#include <iostream>
#include <stdexcept>

namespace utility
{
  class UTILITY_API interval_exception : public std::exception
  {
  public:
    explicit interval_exception(const char *what) :
      m_what(what)
    {}

    const char *what() const throw()
    {
      return m_what;
    }

  private:
    const char *m_what;
  };

  template<typename T>
  class UTILITY_API interval
  {
  public:
    interval();
    interval(const T &min, const T &max);

    bool intersects(const interval &other) const;

    static interval empty();
    static interval infinite();
    static interval hull(const T& min, const T& max);
    static interval intersection_of(const interval &a, const interval &b);

    const T &min() const { return m_min; }
    const T &max() const { return m_max; }

  private:
    T m_min;
    T m_max;

  public:
    friend std::ostream &operator<<(std::ostream &out, const interval i)
    {
      return out << "[" << i.m_min << "," << i.m_max << "]";
    }

    friend std::wostream &operator<<(std::wostream &wout, const interval i)
    {
      return wout << (L"[") << i.m_min << (L",") << i.m_max << (L"]");
    }

    friend bool operator==(const interval &lhs, const interval &rhs)
    {
      return (lhs.m_min == rhs.m_min && lhs.m_max == rhs.m_max);
    }

    friend bool operator!=(const interval &lhs, const interval &rhs)
    {
      return !(lhs == rhs);
    }

    friend bool operator<(const interval &lhs, const interval &rhs)
    {
      return ((lhs.m_max < rhs.m_min) ||
        (lhs.m_min < rhs.m_min && lhs.m_max <= rhs.m_max));
    }

    friend bool operator>(const interval &lhs, const interval &rhs)
    {
      return (lhs.m_min > rhs.m_max) ||
        (lhs.m_min > rhs.m_min && lhs.m_max > rhs.m_max);
    }
  };
}

#endif

---

//Definition
#include <utility/interval.h>
#include <cfloat>
#include <cmath>
#include <limits>

namespace utility
{
  template<typename T>
  interval<T>::interval()
  {
    (*this) = infinite();
  }

  template<typename T>
  interval<T>::interval(const T &min, const T &max) :
    m_min(min),
    m_max(max)
  {
    if (m_min > m_max) {
      throw interval_exception("min must be less than or equal to max");
    }
  }

  template<typename T>
  bool interval<T>::intersects(const interval &other) const
  {
    return (intersection_of((*this), other) != empty());
  }

  template<typename T>
  interval<T> interval<T>::empty()
  {
    return interval<T>(static_cast<T>(0), static_cast<T>(0));
  }

  template<typename T>
  interval<T> interval<T>::infinite()
  {
    if (std::numeric_limits<T>::has_infinity) {
      return interval<T>(-std::numeric_limits<T>::infinity(),
        std::numeric_limits<T>::infinity());
    } else {
      return interval<T>(std::numeric_limits<T>::min(),
        std::numeric_limits<T>::max());
    }
  }

  template<typename T>
  interval<T> interval<T>::hull(const T& min, const T& max)
  {
    if (std::isnan(min) && std::isnan(max)) {
      return interval<T>();
    } else if (std::isnan(min)) {
      return interval<T>(max, max);
    } else if (std::isnan(max)) {
      return interval<T>(min, min);
    } else {
      return interval<T>(min, max);
    }
  }

  template<typename T>
  interval<T> interval<T>::intersection_of(const interval &a, const interval &b)
  {
    if (a.m_min >= b.m_min && a.m_min <= b.m_max) {
      if (a.m_max <= b.m_max) {
        return hull(a.m_min, a.m_max);
      } else {
        return hull(a.m_min, b.m_max);
      }
    } else if (a.m_max >= b.m_min && a.m_max <= b.m_max) {
      if (a.m_min <= b.m_min) {
        return hull(b.m_min, a.m_max);
      } else {
        return hull(a.m_min, a.m_max);
      }
    } else if (b.m_min >= a.m_min && b.m_min <= a.m_max) {
      if (b.m_max <= a.m_max) {
        return hull(b.m_min, b.m_max);
      } else {
        return hull(b.m_min, a.m_max);
      }
    } else if (b.m_max >= a.m_min && b.m_max <= a.m_max) {
      if (b.m_min <= a.m_min) {
        return hull(a.m_min, b.m_max);
      } else {
        return hull(b.m_min, b.m_max);
      }
    } else {
      return empty();
    }
  }

  /// Explicit template instantiations for supported types.
  template class interval<signed char>;
  template class interval<unsigned char>;
  template class interval<wchar_t>;
  template class interval<char16_t>;
  template class interval<char32_t>;
  template class interval<short int>;
  template class interval<unsigned short int>;
  template class interval<int>;
  template class interval<unsigned int>;
  template class interval<long int>;
  template class interval<unsigned long int>;
  template class interval<long long int>;
  template class interval<unsigned long long int>;
  template class interval<float>;
  template class interval<double>;
  template class interval<long double>;
}

Answer 1

Before reviewing the algorithm and its complexity, there is a number of things to be said about the code itself:

• interval<T>::intersection_of should either take an interval to compare to the current interval like interval<T>::intersects does, or keep its design and be a free function. The current design is not intuitive: since the function is in the class, I totally expected it to take an interval and return the intersection of that interval and the current one.

• Your operator<<, operator==... need not be friend. Simply use min() and max() instead of m_min and m_max and you can get rid of these useless friends.

• empty may not be the best name in the world for a construction function. Actually, when reading its name, I expected it to return a bool which would represent whether the interval is empty or not. Agreed, the name is_empty is better for this kind of property, but the standard library uses empty everywhere for that job.

• You could define operator> in terms of operator< so that you don't have to repeat the whole condition:

  bool operator>(const interval &lhs, const interval &rhs)
  {
      return rhs < lhs;
  }
  

• Since your interval class can take any type, it should also be designed to handle big numbers. That means that you could use a bit more move semantics. Take your constructor for example: it could benefit from the pass-by-value idiom:

  template<typename T>
  interval<T>::interval(T min, T max) :
      m_min(std::move(min)),
      m_max(std::move(max))
  {
      // ...
  }
  

  If you make max_scheduling a function template so that it can handle any interval, then you might also want to explicitly std::move the elements that will be popped anyway:

  subset.push_back(std::move(intervals.front()));
  intervals.pop_front();
  

• When you return early in functions, you can generally avoid a lot of else to reduce the visual overhead. For example, you could rewrite hull as such:

  template<typename T>
  interval<T> interval<T>::hull(const T& min, const T& max)
  {
    if (std::isnan(min) && std::isnan(max)) {
      return interval<T>();
    }
    if (std::isnan(min)) {
      return interval<T>(max, max);
    }
    if (std::isnan(max)) {
      return interval<T>(min, min);
    }
    return interval<T>(min, max);
  }
  

• The old function exception specifications with throw() have been deprecated. Now you should use noexcept instead to tell whether your function throws or not:

  const char *what() const noexcept { /* ... */ }