# 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 ...
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 ...
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 ...
Accepted

### Data structure for set of intervals - query for all intervals contains given point

There are many algorithms for this kind of problem. See, e.g., segment trees and interval trees. The kind of query you mention is known as a "stabbing query". A segment tree takes $O(n \lg n)$ ...
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 ...
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$-...

### 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 ...
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 ...
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 ...

### 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 ...
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 ...
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.

### 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 ...
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 ...
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 ...
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']$, ...
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 ...