Interval scheduling problem in C++

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 

#include 
#include 
#include 

/// 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> intervals)
{
  intervals.sort();

  std::list> 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 > input;
  std::stringstream ss;
  ss > test_cases;

  std::list> intervals;
  for (unsigned int test_case = 0; test_case > input;
    ss.clear();
    ss > min;

    std::cin >> input;
    ss.clear();
    ss > max;

    intervals.push_back(utility::interval(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

#include
#include
#include

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

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

-
interval::intersection_of should either take an interval to compare to the current interval like interval::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

-
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

-
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
interval::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
interval interval::hull(const T& min, const T& max)
{
  if (std::isnan(min) && std::isnan(max)) {
    return interval();
  }
  if (std::isnan(min)) {
    return interval(max, max);
  }
  if (std::isnan(max)) {
    return interval(min, min);
  }
  return interval(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 { /* ... */ }

StackExchange Code Review Q#93285, answer score: 4