Questions tagged [intervals]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
2answers
48 views

Max clique in interval graph

According to Efficient algorithms for interval graphs and circular arc graphs there is an $O(n \log n)$ algorithm for finding the max clique in an interval graph, assuming you have the interval model. ...
8
votes
0answers
163 views

2D interval scheduling problem

Suppose I give you $n$ axis-aligned rectangles with a specified width, height, and x-position (of the left edge) $\{(w_i, h_i, x_i) \mid i \in \{0, \ldots, n - 1\}\}$, as well as a bound $(y_\mathrm{...
2
votes
1answer
36 views

Minimum unweighted anticlique (independent set) cover / partition

Suppose I have a set of integer intervals, and I want to generate a visualization like the one attached. One obvious way of accomplishing this is to put every interval in its own row; this obviously ...
3
votes
1answer
24 views

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

Consider a set $P$ of $N$ intervals $\{I_i = (l_i, r_i)\}$ partially ordered according the standard interval order: $I_i < I_j$ iff $r_i \le l_j$. I want to find a minimum cardinality partition of ...
2
votes
1answer
38 views

Queries on knapsack

Given items with weights $w_{1}, w_{2}, \dots, w_{n}$ and queries of form $(l, r, w)$ asking for possibility to find a subset of items $w_{l}, w_{l + 1}, \dots, w_{r}$ with total weight $w$, how to ...
3
votes
1answer
25 views

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$

Let be $(I_n)_n$ a set of $p$ intervals each contained in $[0, L]$ for $L \geq 1$. I define $(J_n = [a_n, b_n])_n$ the set of intervals which have empty intersection with $I_n$ for all $n \in [[1, p]]...
0
votes
0answers
53 views

How Segment trees are used to answer interval stabbing query?

Can anybody explain to me how segment trees are used to answer interval stabbing queries? I have searched and searched and only come with the beginning of the line. From my understanding I need to ...
2
votes
0answers
58 views

Data structure & algorithms for super-interval queries on intervals with small integer ends

I would like to have an online data structure that supports inserting an interval, and given a query interval $I_q=[l_q,h_q]$ answer if some interval of the data structure is contained in $I_q$, i.e. ...
0
votes
2answers
50 views

largest subset of pairwise intersecting intervals [closed]

Given a set of intervals on the real line, compute the largest subset of pairwise intersecting intervals (an interval in the subset must intersect with every other interval in the subset). Design a ...
3
votes
2answers
186 views

Algorithm for detecting overlaps

This is a real-world application, not a student assignment. Suppose a list of events of that have startTime and endTime, and ...
3
votes
0answers
154 views

Algorithm for answering queries of the type “largest interval contained in the given interval”

I have been wondering over the following problem: Given a set $S$ of intervals on the number line. We can do two operations on them: Add a new interval $[l_i,r_i]$ to $S$ Given an interval $[l_j, ...
1
vote
1answer
80 views

How to find the number of intervals containing a point when given a static set of intervals?

I've seen similar questions around here but I'm trying to address this problem with a slight change and maybe it makes it easier to solve. I'm given a set of intervals $\{s_1,s_2,...,s_n\}$ where ...
1
vote
1answer
103 views

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

I have a binary search tree where nodes are non-overlapping intervals. I'm given a point, and I need to determine which interval the point belongs to (if any). This is easy to do because I can compare ...
0
votes
1answer
59 views

Proof for optimal interval scheduling using a Greedy Approach

You are given a set of n jobs, where each job j is associated with a size s(how much time it takes to process the job) and a weight w(how important the job is). Suppose you have only one machine ...
1
vote
2answers
98 views

Algorithm/data structure to quickly check if an integer is a member of any [lower, upper] interval

Are there any existing algorithms/strategies to test if an integer value is within the bounds of any of a list of intervals, where each interval is denoted by a [min, max] pair? The naive approach is ...
1
vote
1answer
66 views

Matching schedules between users and providers

I have a problem I've been dealing for the past few days, and I'm pretty stuck. Each user has a schedule for a given week, such as ...
2
votes
1answer
83 views

Minimal set of subintervals that 'covers' any subinterval in K subintervals

I have a big interval $I = [a, b]$ of size n. I want an asymptotically minimal set of subintervals of $I$ (let's call it $S$) one can use to construct any subinterval of $I$, by concatenating at most ...
1
vote
0answers
42 views

Efficient data structure for multidimensional searching on intervals and keys

I am searching for a data structure that can capture a database, which is consisted of one column of intervals (like [0, 2], [4, 6]) and one/two columns of keys (...
0
votes
2answers
43 views

Sorted unsigned integer intervals tree structure

The goal is to store sorted unsigned integer intervals that can overlap only in the boundaries, e.g., |0–10|10–50|100–110|110–200|. This structure will be created ...
1
vote
0answers
35 views

Sort-of interval scheduling

The Problem I have a set of sets of time intervals (hour, minute, day of the week). I want to select exactly one interval from each of set, and I want to minimize... the number of pairwise ...
2
votes
1answer
50 views

Data Structures - Segment Trees

I was learning about segment trees and came across this: We have an array arr[0 . . . n-1]. We should be able to 1 Find the sum of elements from index l to r where 0 <= l <= r <= n-1 ...
1
vote
1answer
72 views

(M)ILP overlap of two intervals

I got an ILP Model where $c_i$ represents the starting time for a visit$_i$. $c_i$ is already constraint by a number of constraints, one is $c_i > 0$. I have now outside of my model 0 or multiple ...
0
votes
1answer
241 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
70 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
19 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
45 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
58 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
17 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
28 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
20 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
313 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
157 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 ...
2
votes
1answer
45 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 ...
-2
votes
1answer
291 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
182 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
1answer
60 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
562 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
88 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
91 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
205 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
999 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 (...
2
votes
1answer
182 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
225 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 ...
2
votes
2answers
2k 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
645 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 ...
3
votes
1answer
2k 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
2k 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
351 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 ...
3
votes
3answers
2k 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
129 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 ...