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