# Tag Info

Accepted

### How many range are completely inside a given range

I've given an answer to the question with the similar idea here. I'll recall the most important parts of the data structure in this answer. It looks similar to the solution with wavelet trees by Jouni ...
• 887
Accepted

### Best algorithm to find "deepest" interval

Here's an n log n algorithm: Convert the intervals into a sorted collection of start and end events. O(n log n) Initialize a depth value and deepest value to zero, and iterate the collection in ...
• 338
Accepted

### Returning random integer from interval based on last result and a seed

I suggest you pick a random permutation on the range $[a,b]$, i.e., a bijective function $\pi:[a,b]\to [a,b]$. Then, maintain a counter $i$ that starts at $i=a$; at each step, output $\pi(i)$ and ...
• 159k
Accepted

### Given a set of intervals $(I_n)_n$ contained in $[0, L]$, compute the longest interval in $[0, L]$ which has empty intersection with all $(I_n)_n$

(From your notations, I assume the intervals are all discrete as otherwise some of the $J_n$ would not be closed. Furthermore, the length of the intervals would not be $b_n-a_n+1$ so I'm fairly ...
• 1,110
Accepted

### Efficiently locating the maximum value in interval over large amounts of data points

This can be solved with a balanced binary tree. Each such query can be answered in $O(\lg n)$ time. Build a balanced binary tree, where each leaf holds a point, and the tree is keyed on the $x$-...
• 159k

### How many range are completely inside a given range

There are probably existing data structures for this problem, but I am not familiar with them. Instead, I will just create something with the tools I am familiar with. Assume that the ranges are ...
• 462
Accepted

### Are IEEE floating point numbers intervals or point values?

That has been long established. Most IEEE 754 floating point numbers represent exactly one real number. The exceptions are +0 and -0, +Inf and -Inf, and NaN with special meanings. (Thanks for one ...
• 30k
Accepted

### Can we find size of total interval in O(N)

There is a simple $O(n\log n)$ algorithm based on sorting all the endpoints of the intervals. I will describe a more sophisticated algorithm, which outputs the union of the input intervals as a union ...
• 277k

### Computing overlap of intervals in an integer programming framework

By overlap I understand its length (no its coordinates) since you didn't specify how to handle no overlap case. First you need to know whether $x_1\le y_1$ which is just a comparison. Next, you ...
• 386
Accepted

### Finding an interval in a binary search tree that contains a point

You can't find a better algorithm for your problem using comparisons, because a lower bound of $\Omega(\log n)$ can be proven for these setings (proof below). What you can do is some minor ...
• 1,669
Accepted

### Computing minimum partition of poset of $N$ intervals into chains in $o(N^{2.5})$ time?

Your problem is the same as interval graph coloring. There is a well-known greedy algorithm solving the problem optimally, running in linear time if the intervals are already sorted.
• 277k

### Algorithm To Compute The Gaps Between A Set of Intervals

I'd like to propose a quite simple algorithm as well. The idea is this: we're going to place open and close parentheses on the number line at the boundaries of each interval. For example, for the ...
• 1,258
Accepted

### Greedy filling unit intervals

The greedy algorithm Let $result$ be an empty set and let $last\_interval$ be none. For each $num$ in sorted $X$: If $num$ is not covered by the last interval: let $last\_interval$ be the interval ...
• 39k
Accepted

### Compute lebesgue measure of set of intervals

You can solve this in $O(n \log n)$ time. Here is an algorithm. Sort the intervals by their left endpoint ($x$-value), in increasing value. At each stage, if the first interval is disjoint from the ...
• 159k
Accepted

### Find longest overlapping interval

You're just a step away from the answer. Delete all intervals in $S$ which are contained in another interval in $S$. Now $S$ is totally ordered, i.e. for any two interval $[l,r]$ and $[l',r']$, ...
• 515
Accepted

### Algorithm To Compute The Gaps Between A Set of Intervals

The key to prove your algorithm is correct is to find enough invariants of the loop, step 4 so that we apply use mathematical induction. Let $I_1, I_2, \cdots, I_n$ denote the sorted intervals. When ...
• 39k

### Maximum interval scheduling - Circular Variation

Yes. What we need to do is, basically, running the $O(n^2)$ algorithm provided in the question, but without unnecessary intervals and redundant steps. Here is the gist of an $O(n\log n)$ algorithm. ...
• 39k
Accepted

• 364