This solves instances of the weighted interval scheduling problem and visualizes its solutions. It shows text-based output and also plots all input intervals, highlighting the ones that are part of the solution it found.
This is alpha 4 of weighted-intervals. The web version is implemented,
though there are some bugs and missing features. See BUGS.md. The
CLI version is not yet implemented (except in the sense that you could import
wi.py and interact with it as you please).
Try weighted-intervals on the web here.
ALGORITHM.md describes the algorithm I used and compares it
to other algorithms for this problem.
weighted-intervals is written by Eliah Kagan. It is licensed under
0BSD. See LICENSE.
Its dependencies are written by different authors and have
different licenses, though they are all free open-source software. Furthermore,
none of them are included in this repository—they are obtained from CDNs
(for the web version) or via pipenv (if you
work locally and use the provided
Pipfile/Pipfile.lock). So this whole repository
is offered under 0BSD.
Given a set of weighted intervals, where each interval’s start time is strictly less than its finish time, and each weight is strictly positive, the goal is to find a subset of intervals that maximizes the sum of all the weights. The weights are sometimes called values; their sum is known as the total weight, or cost.
I wrote this program to explore a particular algorithm, which runs in O(n2) time on n intervals. Although this algorithm is faster than a O(2n) brute force check of all subsets, it is not the fastest algorithm; the problem can be solved in O(n log n) time with dynamic programming. It is possible that a future version of this program might showcase multiple algorithms (which would be valuable in part because different algorithms can pick different equally good subsets as solutions).
For information on the algorithm used, and how it relates to other algorithms,
see ALGORITHM.md (and docstrings in wi.py).
This describes how the web version of the software works, not the algorithm it
uses. In summary: a whole Python interpreter runs in your web browser, and the
interesting code is in wi.py.
The algorithm used here could be implemented in just about any language, including JavaScript, but I’ve used Python, which I think is a nice language for expressing algorithms to humans while still letting them run (albeit not always as fast as in some other languages). But Python code does not traditionally run in web browsers.
The web version of weighted-intervals uses Pyodide to run a Python interpreter in the user’s web browser. Pyodide supplies and runs a WebAssembly port of CPython.
Intervals are plotted using Matplotlib, a popular Python library. Pyodide supplies packaged/ported versions of Matplotlib and its dependencies.
wi.py contains the weighted-interval scheduling implementation as
well as the visualization code. bridge.js uses Pyodide to run
code in wi.py and to marshal data between Python and JavaScript.
It would be clearer—and better software engineering—to put the
algorithmic code and the visualization in separate Python modules, rather than
having both in wi.py. I haven’t done that yet because of the
way I’m having Pyodide load wi.py—by downloading its
contents and executing them in the Python interpreter. This places everything
in the global namespace, unlike what happens when a module is imported. Doing
this with multiple modules would be confusing even if there are no clashes. (If
necessary, I can solve this by packaging my Python modules in a
wheel.)
Until then, if one is just interested in the algorithm implementation, one
might prefer to look at the shorter wi.py from alpha
0.
The dependencies are obtained externally rather than being included in this repository.
weighted-intervals uses these libraries:
- Pyodide 0.25.0, by the Pyodide development team (Mozilla Public License 2.0). This supplies a WebAssembly port of CPython 3.11.3 and various libraries. All recent versions of CPython itself are licensed under the Python Software Foundation License 2.0.
- Matplotlib
3.5.2
by the Matplotlib Development Team. Matplotlib is licensed under the License
agreement for matplotlib versions 1.3.0 and
later.
It includes some components by other authors with other licenses. See the
Matplotlib license page
and the files in the Matplotlib
LICENSEdirectory for further details. - normalize.css 8.0.1 by Nicolas Gallagher and Jonathan Neal (MIT License)
- Fork me on GitHub CSS ribbon 0.2.3 by Simon Whitaker (MIT License)
And these fonts:
- Source Sans Pro, designed by Paul D. Hunt and licensed under the SIL OFL 1.1 (© Adobe, with reserved font name “Source”). This font is now called Source Sans 3 in the current version, but I’m using Source Sans Pro, an earlier version.
- Source Code Pro, designed by Paul D. Hunt and licensed under the SIL OFL 1.1 (© Adobe, with reserved font name “Source”).
I’d like to thank:
- Professor Aparna Das, who introduced me to the weighted interval scheduling problem and to the work of Jon Kleinberg and Éva Tardos on this problem.
- Jon Kleinberg and Éva Tardos, who presented a different (and better) solution than mine to this problem, in Algorithm Design, 1st ed. (pub. 2006), sec. 6.1, pp. 252-260; and Kevin Wayne, who made reference slides on that material, which I also found useful.
- The authors/contributors of the dependencies listed above.
(None of those people is responsible for bugs in this program or in its documentation.)