jtr@cs.exeter.ac.uk (Jason Trenouth) (08/26/88)
Here's a problem for a sleepy news network. I apologise if its in Knuth or somewhere - I ain't checked. The data: The data to manipulate consists of lists (doesn't it always) of intervals. These intervals are disjoint, and ordered (always same way). The problem: Write two efficient predicates: one to compute the intersection, and one to compute the union of two such lists. An example: Given [2-4, 5-7, 10-19] and [1-3, 4-15, 20-20] Intersection = [2-3, 4-4, 5-7, 10-15] Union = [1-19, 20-20] An order N+M solution exists for each algorithm where N and M are the number of intervals in the length of the two lists. Have fun - JT. -- ______________________________________________________________________________ | Jason Trenouth, | JANET: jtr@uk.ac.exeter.cs | | Computer Science Dept, | UUCP: jtr@expya.uucp | | Exeter University, Devon, EX4 4PT, UK. | BITNET: jtr%uk.ac.exeter.cs@ukacrl|