Top-nodes Algorithm - Principle

Principle

The calendar is stored as a binary tree where leafs represent elementary time periods. Other nodes represent the period of time covered by all their descendants.

Example of a 7-hour calendar (with elementary periods of one hour)

The period of time covered by a reservation is represented by a set of "top-nodes". This set is the minimal set of nodes that exactly cover the reservation period of time.

A node of the binary tree is a "top-node" for a given reservation if

  • all its descendants are inside the reservation period of time,

and

  • it is the root node, or at least one descendant of the parent node is outside of the reservation period of time.
Top-nodes for a reservation from 1:00 to 5:59

The following value is stored in each node:

q(node) = max(q(left child), q(right child)) + total amount of reserved resource for all reservations having this node as a "top-node"

(for code optimization, the two parts of this sum are usually stored separately.)

Read more about this topic:  Top-nodes Algorithm

Famous quotes containing the word principle:

    “Now, what I want is, Facts. Teach these boys and girls nothing but Facts. Facts alone are wanted in life. Plant nothing else, and root out everything else. You can only form the minds of reasoning animals upon Facts: nothing else will ever be of any service to them. This is the principle on which I bring up my own children, and this is the principle on which I bring up these children. Stick to Facts, sir!”
    —Charles Dickens (1812–1870)

    “Why does philosophy use concepts and why does faith use symbols if both try to express the same ultimate? The answer, of course, is that the relation to the ultimate is not the same in each case. The philosophical relation is in principle a detached description of the basic structure in which the ultimate manifests itself. The relation of faith is in principle an involved expression of concern about the meaning of the ultimate for the faithful.”
    —Paul Tillich (1886–1965)

    “I sincerely believe ... that banking establishments are more dangerous than standing armies, and that the principle of spending money to be paid by posterity, under the name of funding, is but swindling futurity on a large scale.”
    —Thomas Jefferson (1743–1826)