Path: csiph.com!aioe.org!.POSTED!not-for-mail From: =?UTF-8?Q?Arne_Vajh=c3=b8j?= Newsgroups: comp.lang.java.programmer Subject: Re: Wanted: List of intervals Date: Sun, 19 Feb 2017 22:52:09 -0500 Organization: Aioe.org NNTP Server Lines: 41 Message-ID: References: NNTP-Posting-Host: PBuS014lhzVyHjLbXmo/ZQ.user.gioia.aioe.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit X-Complaints-To: abuse@aioe.org User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:45.0) Gecko/20100101 Thunderbird/45.7.1 X-Notice: Filtered by postfilter v. 0.8.2 Xref: csiph.com comp.lang.java.programmer:36350 On 2/19/2017 5:18 PM, Eric Sosman wrote: > On 2/19/2017 5:13 PM, Arne Vajhøj wrote: >> On 2/19/2017 2:02 PM, Robert Klemme wrote: >>> On 17.02.2017 04:32, Arne Vajhøj wrote: >>> >>>> If that example is realistic then you can simply: >>>> * allocate byte array of suitable length >>>> * loop through intervals and mark corresponding bytes >>> >>> What are "corresponding bytes"? Do you want to use the byte array as a >>> bitset and mark all bits corresponding to values inside intervals? >> >> Yes. >> >>>> * loop through bytes and create new intervals >>>> >>>> But if the numbers really need to be long aka is greater >>>> than MAX_INT, then that strategy does not work. >>> >>> Even for ints the approach seems pretty wasteful, if I understood you >>> correctly. >> >> I am not so sure about that. It is O(n) in number of intervals. >> No sorting required. > > If I understand you correctly, the time should be O(n+m) > for n intervals containing a total of m bytes. I would call that O(N) in number of intervals and O(N) in interval length. Where the sorting solution is O(NlogN) and O(1). > Memory use > would be O(biggestOffset - smallestOffset). O(N) with some assumptions. Arne