# Tag Info

11

The claim is that there are at most $2$ nodes which are expanded at each level. We will prove this by contradiction. Consider the segment tree given below. Let's say that there are $3$ nodes that are expanded in this tree. This means that the range is from the left most colored node to the right most colored node. But notice that if the range extends to ...

6

There is an $O(n \log n)$ time algorithm (which in some models is optimal, because of the bounds for the element distinctness problem). We first sort the intervals by their right end point. Suppose the sorted order is $I_1, I_2, \ldots, I_n$. Now for each interval, we try to compute the size of the largest possible non-intersecting set, with that interval ...

5

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 but, I think, is easier to code (arguable). Here is the data structure which is sometimes called Merge Sort Tree. It is basically a segment tree where each ...

5

You can solve it in $O(n \lg n)$ time using a divide-and-conquer algorithm. Explaining the main idea: a cleaner variant To help me explain the main idea, I'm going to change the problem slightly. I'll assume we're given a set of intervals, with no interval appearing more than once in the set, and where for any pair of overlapping intervals $I,I'$, one of ...

5

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)$ space, can be built in $O(n \lg n)$ time, and can answer a stabbing query in $O(k + \lg n)$ time, where $n$ is the number of intervals and $k$ is the number of ...

5

This is called the "Interval Scheduling" problem in the book [1]. The greedy algorithm, along with an example, is as follows (please find the correctness proof in the book mentioned above): sort the intervals in increasing order of their finishing times, still denoted as $\mathcal{I}$. while ($\mathcal{I} \neq \emptyset$) choose the first $I \in \mathcal{I}... 5 (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 certain that assumption is safe. If however that was not your intention, it should be straightforward enough to adapt the algorithm to the continuous case). Consider ... 5 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 then increment$i$(wrapping around so that$b+1$becomes$a$). There are standard methods for generating such a random permutation in the cryptography literature: ... 4 I believe logarithmic time for all queries is achievable. The main idea is to use an interval tree, where each node in the tree corresponds to an interval of indices. I'll build up the key ideas by starting with a simpler version of the data structure (that can support get and set but not the other operations), then add features to support the other ... 4 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$-coordinate of the points (so the leaves contain the points, sorted from left to right). Augment the tree, so that in each node$t$of the tree, you store a pointer ... 4 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 stored in arrays$A$and$B$so that$A[i] = a_i$and$B[i] = b_i$and that the ranges are sorted by their starting points. Given a query range$[c, d]$, we can ... 4 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 of internally disjoint intervals (they may have overlapping endpoints). Denote the input intervals by$[s_i,t_i]$. Initialize a variable$a$to 0. This ... 3 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 second interval, remove the first interval and add its width to the running total so far. If they're not disjoint, replace the first two intervals by their ... 3 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']$, either$l<l'$and$r<r'$or$l>l'$and$r>r'$. Now it's not hard to find the first interval$[l,r]$s.t.$l\ge i$and the last interval$[l',r']$s.t.$r'...

3

The problem requires $\Omega(n)$ time. Consider the interval $[A,B] = [0,N]$ and an algorithm for the problem. Whenever the algorithm queries $[S_{i1},S_{i2}]$, it gets the answer $[i-1,i]$. If the algorithm queries all intervals, then it knows that they cover $[A,B]$. Otherwise, the algorithm cannot tell. Indeed, suppose that it doesn't query $[S_{i1},S_{i2}... 3 Imagine scanning the real line from left to right. Whenever an interval starts or ends, you make notice of it. For example, perhaps at some representation, at the point$3$the intervals for$x_2,x_7$start and the interval for$x_{15}$ends, and at the point$4$the interval for$x_2$ends, and no points occur in between. Suppose we "remove" the portion$(...

3

This is called Interval Partitioning Problem or Interval Coloring Problem in this lecture note, as well as in Section 4.1 of the book [1]. Given intervals $(s_i, f_i)$, assign them to processors/workers so that you schedule every interval and use the smallest number of processors/workers. The greedy algorithm is a simple one-pass strategy that orders ...

3

What about another sorting order, which seems to be compatible with pre-order in your proposed trees? Define $I \le I'$ with $I=[a,b]$ and $I'=[c,d]$ iff $I$ is before $I'$, i.e., $b\le c$, of $I$ contains $I'$, i.e., $a\le c$ and $d\le b$.

3

Store your IP address as an integer or long depending on whether it is 32 or 64 bit. Then put the ranges into an interval tree or similar data structure that will allow you to find all ranges that intersect with a given range or point (in this case the IP address you want to check against). This will have a query time of O(lg N) after a preprocessing time of ...

3

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 create new variables $l_1, l_2, r_1, r_2$ for which you know that $l_1\le r_1, l_2 \ge l_1, r_2 \ge r_1$ Now the answer is $\min(\max(l_2 - r_1, 0), r_2 - r_1))$ ...

3

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 optimizations; if each node in your tree saves the end of the rightmost segment and the beginning of the leftmost segment, by adding $2$ comparisons to each query, you ...

3

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.

2

To a mathematician "prove or disprove" is a very strict requirement. I do not know how serious I should take this. Every tree that has been implemented using pointers also has a array implementation. The trick is to do the addresses yourself as indexes to an array. That is usually called a cursor implementation. Binary trees can be implemented, as you say, ...

2

I would suggest looking at interval trees and segment trees. A natural representation is that the data structure contains a union of non-overlapping ranges $[l,u]$ with a multiplicity $m$; the intended meaning is that each integer in the range $l,l+1,l+2,\dots,u$ occurs in the domain with multiplicity $m$ (i.e., appears $m$ times), and the invariant is that ...

2

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. If you tried to claim that IEEE 754 floating point numbers did represent intervals, then you would run into deep, deep trouble when you try to define floating-point arithmetic.

2

You were too quick to reject interval trees and segment trees. You can search an segment tree for all intervals that are contained in a query interval $q=[\ell_q,u_q]$, using a straightforward recursive procedure: Any node $v$ of a segment tree has a corresponding interval $\text{Int}(v)$. Do a recursive search of the tree, except that you only visit ...

2

Sort all coordinates of intervals (annotated with their significance), and scan them in order. As an example, in your case you would get $$1^{+red},5^{+yellow},7^{+green},8^{-green},9^{-yellow},11^{-red},15^{+black},16^{-black}$$ This immediately gives the decomposition into intervals $$(1,5),(5,7),(7,8),(8,9),(9,11),(11,15),(15,16)$$ with associated ...

2

It is a very strong assumption that the time it takes to preprocess is not a concern. Assume each given interval contains both of its endpoints. Otherwise, the solution below can be adapted easily. Sort all $b_i$ and $r_i$ into an increasing sequence $A=(a_1, \cdots, a_{2n})$. Let $c_1=1$. For $i$ from 2 to $2n-1$, let c_{i}=\begin{cases} c_{i-1}+1&...

2

I suppose you want to delete as little EmptyEvents as possible. In that case, you can achieve what you want in O(nlog(n)) time, where n is the number of events. Proceed as follows: First, get rid of the EmptyEvents which overlap with a NormalEvent. To do so, put all your starting and ending times in a vector and sort them in increasing order, breaking ...

2

@Tassle algorithm works great but needs more explaining for vectors ordering. To do so, put all your starting and ending times in a vector and sort them in increasing order, breaking ties by putting end-times before start-times. Set a counter = 0 and an empty unordered set S. Now go through your vector of times in order. The priority for the first ...

Only top voted, non community-wiki answers of a minimum length are eligible