# 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 <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>;
}


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 { /* ... */ }

• Perhaps changing the static function names to set_hull, set_empty etc might help remove some of the ambiguity with how the standard library names its functions. That said I am still interested to see if you have found any bugs in the code and your analysis of the algorithm itself. That said I appreciate the review thus far. Jun 11, 2015 at 14:23
• @MatthewHoggan I may try to find algorithmic problems and/or improvements, but it requires more analysis and I'm kind of lazy today. The set_* would look like setters. I would name the functions empty_interval or create_empty, even if it makes the names longer, it reduces the risks of thinking that they do something else. Jun 11, 2015 at 14:26
• @MatthewHoggan Or you could create free functions named make_empty_interval and make_inifinite_interval. That would leave no possible confusion. Jun 11, 2015 at 14:27