Path: utzoo!attcan!uunet!mcvax!ukc!warwick!expya!jtr From: jtr@cs.exeter.ac.uk (Jason Trenouth) Newsgroups: comp.lang.prolog Subject: Sequence Of Intervals Problem Message-ID: Date: 25 Aug 88 20:19:13 GMT Sender: jtr@cs.ex.ac.uk Organization: Computer Science, Exeter University, UK. Lines: 32 Posting-Front-End: GNU Emacs 18.41.4 of Tue Feb 23 1988 on expya (berkeley-unix) 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|