This idea requires a bit of set up, but it only goes through the lists twice (eg O(n+m), instead of O(n*m)) with one sort (O(nlogn)).

For each iterval, add 2 items to a hash, one with key:value of the start time and a unique interger (eg $i++); the second with the end time and the negative of that integer.

For each even, add one item to the same hash, key the event time, and value 0.

Grab the keys of the hash, and sort on time, with secondary sort on the ascending order of the absolute value of the hash value Eg, for three values with teh same key, the order would be something like 0, -3, 5.

Now, just iterate along the keys. If the value of a key is a positive integer, then in another hash (interval_hash), set that key to some value (eg, if the integer is 3, the interval_hash would be key 3, value 1). If a negative interger, undef that value from the interval_hash. If zero, then in a third hash (occured_hash), for each key currently in interval_hash, push the time onto an array for that interval. So, if time is currently 10, and interval_hash contains keys 3, 4, and 7, then for occured_hash keys 3,4, and 7, you'd push 10 onto the arrays that are referenced by this.

When you are all done, then the values for a given interval key in occured_hash will be an array with all the times that fall into those events.

Again, this should be faster based on the order calculations, but you'd have to try it out and make sure that the little things like hash manipulations don't slow it down too much (it shouldn't).

UPDATE: ok, the trick on the secondary sorting (dealing with intervals and events that occur at the same time), partially has to do if you want inclusive or exclusive intervals. If you want inclusive, then the secondary sort should be in decending, non-absolute order (eg 5, 0, -3 ), such that you 'initiate' new intervals before you process the events, and then 'deactivate' any intervals after processing. If you want 'exclusive', then sort in increasing order (-3, 0, 5) to delete intervals before dealing with events, then creating new ones.

Dr. Michael K. Neylon - mneylon-pm@masemware.com || "You've left the lens cap of your mind on again, Pinky" - The Brain

In reply to Re: Assemble times into ranges by Masem
in thread Assemble times into ranges by Dominus

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.