The intervals tag has no usage guidance.
0
votes
1answer
26 views
interval scheduling algorithm
can any one explain why the greedy algorithm solution i.e sorting according to finishing time is optimal in the interval scheduling algorithm ?? I want proof in layman's language. I was watching this ...
1
vote
1answer
38 views
Variant of interval scheduling with varying task durations
I am probably just missing the correct term for my problem to find the solution but here it goes:
I have a set of tasks with a given duration and an interval for each task in which it has to be ...
2
votes
1answer
16 views
Array of overlaping ranges
Consider that I have an array of ranges and I want to transform it to the new array that represents the ranges that any range is in.
Example:
Ranges:
[red: [1,11], black: [15,16],yellow: [5,9], ...
3
votes
0answers
34 views
Compile-time error control vs. interval arithmetic?
I use interval arithmetic for reliable computing. Now, a procedure coded in a good implementation of interval arithmetic takes perhaps about eight times as much as the same procedure carried out ...
1
vote
1answer
45 views
Candy Problem for k size window
I was solving this problem and end up learning two ways to solve this problem. One is two pass method and the other is considering peak and valleys (candies - interviewstreet). Both of these are O(n) ...
2
votes
0answers
11 views
Segment-tree construction: do we recurse into both children?
This question is about segment-tree as described in this Wikipedia article.
When constructing the tree (inserting the new input-interval), if the input-interval doesn't contain the node-interval we ...
0
votes
1answer
21 views
Interval Scheduling Confusion
I am reading some notes about interval scheduling. I gives the following diagram:
and states that:
r2 is compatible with r3, while r2 and r1 are conflicting. Similarly, the set {r1, r3, r4} is ...
-1
votes
1answer
16 views
Find longest interval if the intervals can propagate from one to another
Let's say we have given $n$ points on the x-axis, each point described with two integers: $x_i, a_i$, $x_i$ meaning it's position on the x-axis, and $a_i$ meaning that it can activate all the points ...
1
vote
1answer
141 views
Finding the longest overlapping interval pair
Say I have a list of $n$ integral intervals $[a,b]$ where each represents a set $S = \{a, a+1, \ldots, b\}$. An overlap is defined as $|S_1 \cap S_2|$. Example: $[3,6]$ and $[5,9]$ overlap on $[5,6]$ ...
3
votes
0answers
90 views
Construct polygons from axis-aligned intervals
Scenario
Consider one or more curved shapes in 2D space, clipped to a rectangular viewport. For example:
Unfortunately, data that would describe these shapes precisely, is not available.
Input data
...
3
votes
1answer
39 views
Can we find size of total interval in O(N)
Let's say we have given $N$ intervals in the form $[x, y]$, both $x,y$ are integers , we want to find the number of integers covered by at least one interval of all $N$ intervals, (look in the ...
-1
votes
1answer
102 views
Obtain data structure able to do reverse range updates
For given array $A$ of size $N$, note that the array is going to be permutation of the numbers from 1 to N, each number will be there exactly once, we want to obtain data structure being able to ...
1
vote
1answer
57 views
Computing overlap of intervals in an integer programming framework
Suppose I have 2 intervals C1 = [x1, x2] and C2 = [y1, y2], where x1,x2,y1,y2 are variables in an Integer program, I want to compute the overlap of C1 and C2. I am interested in a tight formulation ...
0
votes
0answers
33 views
Minimal hitting sets of an interval hypergraph
Given an interval hypergraph $H = (V,E)$, where $V \in \{1 \ldots n\}$ and $E$ is a set of subsets of consecutive elements of $V$, are the minimal hitting sets of $H$ polynomial in number?
Below is ...
0
votes
1answer
44 views
Check if current interval is overlapping some intervals, or is being overlapped
Let's say we have array of $K$ integers, and we have given $N$ intervals in the form $l_{i}, r_{i}$, both inclusive, the interval $i$ means that all elements in the range $[l_i, r_i]$ are covered. Our ...
0
votes
1answer
315 views
Troubles understanding this Interval Scheduling question
Can someone explain how to prove what this question is asking? I'm terrible at proofs and the fact that I don't even understand the hint is very troubling. This is a homework question.
Consider the ...
2
votes
1answer
59 views
how to prove original intervals and canonical form of intervals have the same interval graph
According to this paper,a family of intervals is said to be canonical if the coordinates of the endpoints of the intervals are distinct integers between 1 and 2n where n is the number of intervals.
...
1
vote
1answer
69 views
Compute lebesgue measure of set of intervals
Let $S = \{ [x_1, y_1], [x_2, y_2], \dots, [x_n, y_n] \}$ be a set of not necessarily disjoint intervals on $\mathbb{R}$. Is there an efficient way to compute the lebesgue measure of the union
$\...
2
votes
2answers
97 views
Canonical representation of finite maps on non-overlapping finite rational intervals
I would like to have a canonical representation of a map from rational intervals (f, t] with f, t ∈ ℚ to some irrelevant value type. These intervals are non-overlapping and there exist only finitely ...
1
vote
1answer
452 views
Find all intervals that are contained in a query interval
Given a set of intervals $S = I_1, ..., I_n$, what is the fastest way to find all intervals of $S$ that are completely contained in an interval $I_\text{query}$? It should also support incremental (...
3
votes
1answer
120 views
Check whether an interval is contained in a union of intervals
Initial Problem:
Given an interval $[A, B]$ and a set of intervals $S = \{[S_{11},
S_{12}], [S_{21}, S_{22}], [S_{31}, S_{32}], \ldots, [S_{N1}, S_{N2}]\}$
with $S_{11}\leq S_{21}\leq \cdots \leq ...
2
votes
1answer
178 views
Are IEEE floating point numbers intervals or point values?
The context is IEEE 754-2008 floating point number systems. The systems defined by the standard comprise, as far as I understand it, a bit-level representation and a set of guarantees on the precision ...
3
votes
2answers
661 views
Interval tree: find all intervals containing a given interval
Given an interval tree $T$ and an interval $I$, I need to find an algorithm that returns all intervals in $T$ that contain $I$. The asymptotic running time should be $O(min(n,(k + 1) log n))$ where $k$...
1
vote
1answer
377 views
Interrupts and polling
Are Interrupts really just an abstracted form of polling?
I saw a system-file-watcher library that stated it used polling, as opposed to listening for events. Is the .NET framework SystemFileWatcher ...
2
votes
1answer
1k views
Find longest overlapping interval
Given a set $S$ of $n$ overlapping intervals, where each interval is in the range of [1..O(n)], preprocess $S$ so we can efficiently answer the following query:
Given an interval [i,j] output the ...
2
votes
2answers
603 views
Find minimum number of time points that cross out all intervals
Say we have a set of time intervals, that may intersect. A time point "marks" all of the intervals that are still unfinished at that time point. I wish to find an algorithm so that I can mark all of ...
0
votes
0answers
227 views
Interval scheduling, unclear greedy proof
I am having trouble understanding the proof of the theorem, which states that the greedy scheduling algorithm produces solutions of maximum size for the scheduling problem.
The proof that I am ...
4
votes
3answers
630 views
How many range are completely inside a given range
I have a list of ranges ai , bi. And I have many queries in the form of a range c, d, which asks how many ranges ( ai, bi ) are completely inside c, d.
c <= ai & bi <= d
There are so ...
1
vote
0answers
113 views
Interval scheduling with choice of interval per job
Interval Scheduling problems present several intervals that may overlap and the usual goal is to find the greater set of non overlapping intervals.
Variations of the problem on wikipedia and such add ...
1
vote
0answers
644 views
Why is it necessary to sort according to the starting time in the interval partitioning problem?
What is the problem if we sort the intervals according to their finishing time like the interval scheduling problem? Could someone give a counterexample
?
Note- (refer here for detailed definition)
...
2
votes
0answers
391 views
Some confusion about segment tree and line sweep method for finding area of union of axis parallel rectangles
I am having some confusion about finding the area of union of $n$ axis parallel rectangles in $O(n\log n)$ by the line sweep method. The following pictures are from the book of Shamos and Preparata.
...
2
votes
2answers
146 views
Efficient immutable data structure for small multi-sets of integer ranges?
Background
I'm currently writing some Elixir algorithms that are quite computationally expensive. The most-used datastructure is a multi-set of (finite) integer ranges. Modifying this data structure ...
1
vote
1answer
156 views
Efficiently locating the maximum value in interval over large amounts of data points
I have a set of $n$ two-dimensional data points $(x_i,y_i)$. I want to efficiently answer the following query: Given an arbitrary interval of $x$-values, find the highest and lowest points within ...
4
votes
1answer
224 views
Delete a consecutive range of leaves from a binary tree
Suppose I have a binary tree containing $n$ leaves and whose depth is $d$, where the data is in the leaves (the internal nodes don't hold data values).
I want to delete a consecutive interval of ...
0
votes
1answer
993 views
Data structure for set of intervals - query for all intervals contains given point
We're given a set of $n$ intervals $[a_i, b_i]$, $i=1...n$.
I am looking for a data structure which makes it possible to query for all intervals that contain the point $x$.
My proposition is using ...
0
votes
0answers
47 views
Given $m$ operations of coloring. What is color of $i$-th ball ?
There are given $n$ balls. Their indexes: $\{1,...,n\}$.
Initially all of them are painted in $green$. (other possible color in my problem is $red$).
It is possible to paint interval of balls in color ...
0
votes
1answer
2k views
Interval scheduling scheduling problem with minimal workers
I am writing a greedy algorithm for a variation of the interval scheduling problem that I haven't seen before.
I have a set of jobs, each with start and finish time. All jobs in set must be assigned ...
5
votes
2answers
1k views
Algorithm: ordering non-overlapping intervals
Assume we have a (multi)set of nontrivial intervals $\mathcal{I} = \{I_1,...,I_n\}$ and for any two $I_i, I_j \in \mathcal{I}$, we have that $I_i \cap I_j$ is trivial (that is: contains at most one ...
6
votes
1answer
4k views
Time Complexity proof for Segment Tree implementation of the ranged sum problem
I understand that segment trees can be used to find the sum of sub array of $A$. And that this can done in $\mathcal{O}(\log n)$ time according to the tutorial here.
However I'm not able to prove ...
8
votes
1answer
682 views
Find set of points with maximum distance inside given intervals?
Let $A$ be a set of $n$ closed intervals, $I_i$, with both extremes positive integers. Is there an efficient algorithm to find a set of $n$ points $P_i$, with $P_i \in I_i$, such that the minimum ...
2
votes
1answer
481 views
Supporting queries for finding how many intervals in a dynamic set of 1D intervals contain a given point
You want to create a data structure that can store 1 dimensional intervals and also support the query for finding the total amount of intervals intersecting a given point.
One solution would be for ...
1
vote
1answer
410 views
Implementing an interval tree using arrays?
Is it possible to create an interval tree using an array instead of the traditional pointer method? I know that for segment trees this is commonly done where the children of any element with index i ...
3
votes
0answers
429 views
Range bit inversions and range set bit queries with a binary indexed tree
I am trying to solve this problem using a binary indexed tree. The problem can be summarized as follows:
You are given a series of commands that operate on an array initially
all zeroes.
1) ...
1
vote
1answer
2k views
How to find an IP in overlapping ranges of IPs?
I have a large number (millions) of IP ranges which might overlap. An IP range should contain the start IP, stop IP and an range id. How can I efficiently find which ranges contain a given IP?
I ...
3
votes
1answer
477 views
Efficient algorithm for detecting overlaps in time intervals
Let's say I am building a time clock app. The employee can log into the interface and then enter time for multiple projects so that we can generate reports for billing as well as payroll.
A table in ...
0
votes
1answer
103 views
Recognizing interval graphs--“equivalent intervals”
I was reading a paper for recognizing interval graphs. Here is an excerpt from the paper:
Each interval graph has a corresponding interval model in which two intervals overlap if
and only if ...
0
votes
1answer
222 views
The most frequent integer value from set of intervals [closed]
What is the fastest way to get one of the value from set of intervals which occurs most frequently?
For example if I have interval (0, 3) and (2, 4) the most frequent value can be 2 or 3.
3
votes
1answer
198 views
What is this problem? Largest set of contiguous x values for which the same y value can be held
I'm trying to find a linear solution with a small constant factor but I'm not sure what to search for, or even how to succinctly describe it. The best I've come up with is:
Given a set of ...
3
votes
1answer
671 views
Algorithm to determine if an interval is covered by a list of intervals? [closed]
Given a list of intervals $[s_1, e_1], [s_2, e_2], \ldots$, what's the most efficient way to determine if an interval $[a, b]$ can be covered by the intervals in the list?
11
votes
1answer
1k views
Data structure for map on intervals
Let $n$ be an integer, and let $\mathbb{Z}$ denote the set of all integers. Let $[a,b]$ denote the interval of integers $\{a,a+1,a+2,\dots,b\}$.
I am looking for a data structure to represent a map $...
