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

8

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 sorted order. O(n) When you encounter a start event, increment your depth value. If it's greater than the deepest you've seen, update your deepest and save the ...

7

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

6

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

5

This is called the "Interval Scheduling" problem in the book . 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 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 (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 ... 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 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 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 comment stating that "In IEEE Std 754-2008, Table 3.1 states that floating point numbers are projected into the (extended) reals, which implies that indeed ... 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 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))$... 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 ... 4 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. 4 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 the algorithm has just finished processing$I_i$, we record the values of gaps and last_covered_point as$\text{gaps}_i$and$\text{last_covered_point}_i$... 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

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 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 This is called Interval Partitioning Problem or Interval Coloring Problem in this lecture note, as well as in Section 4.1 of the book . 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 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 ... 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 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 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}...

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

I think your problem is actually not a scheduling problem but a set cover problem. Just cut the time line in the atomic time parts of providers and assign them indices. For instance, considring only one day for user from 8h to 14h: provider 1: 7h-10h provider 2: 6h-9h provider 3: 10h-16h The cut-off is: 6h-7h 7h-9h 9h-10h 10h-16h and your problem is ...

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

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