3
\$\begingroup\$

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>;
}
\$\endgroup\$
3
\$\begingroup\$

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 { /* ... */ }
    
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Matthew Hoggan Jun 11 '15 at 14:23
  • \$\begingroup\$ @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. \$\endgroup\$ – Morwenn Jun 11 '15 at 14:26
  • \$\begingroup\$ @MatthewHoggan Or you could create free functions named make_empty_interval and make_inifinite_interval. That would leave no possible confusion. \$\endgroup\$ – Morwenn Jun 11 '15 at 14:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.