Questions tagged [intervals]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
22 views

Find if union of discrete intervals with holes covers the whole interval space

There is a whole space interval [0,128] And several discrete sequences like: ...
user avatar
3 votes
1 answer
148 views

Greedy filling unit intervals

I have unit intervals given such as $I = \{\{s_1, s_1 + 1\}, ..., \{s_k, s_k+1\}\}$ ($\forall s_i \in \mathbb{R}$). I am given a list of $X$ reals, such that each of the reals belongs to at least one ...
user avatar
  • 149
1 vote
1 answer
33 views

Is there a data structure for lazy-loading time-series data?

I am writing a UI that needs to display a chat log, similar to Slack and Discord. In addition to being able to scroll and lazy-fetch additional pages in either direction, I need to be able to jump to ...
user avatar
3 votes
1 answer
56 views

Bisecting Intervals of floating point numbers containing 0 and infinity fairly

It is seldom considered that floating points are not evenly distributed in the real number line. I've been working with interval arithmetic and noticed when bisecting $[a,b]$ on the real number line ...
user avatar
0 votes
1 answer
46 views

Interval Tree by Augmenting an AVL Tree

According to Wikipedia: An augmented tree can be built from a simple ordered tree, for example a binary search tree or self-balancing binary search tree, ordered by the 'low' values of the intervals. ...
user avatar
1 vote
0 answers
31 views

Data structure for quickly obtaining all axis-aligned rectangles completely within rectangular region

I'm stuck on a homework assignment. There are $n$ axis aligned rectangles and we need to find a data structure of size $O(n \log^2 n)$ and query time $O(\log^3 n + k)$ that can give all rectangles ...
user avatar
  • 11
0 votes
1 answer
318 views

Best algorithm to find "deepest" interval

Let's say I have a list of intervals on a number line. The "depth" of a point on this number line corresponds to the number of intervals in the list that contain it [the point]. So for ...
user avatar
  • 111
3 votes
1 answer
62 views

Weighted maximum match for intervals

Say I have two sets of intervals sorted by time $I_1=[(x_1, y_1),... (x_n, y_n)]$ and $I_2 = [(a_1, b_1)... (a_m, b_m)]$. where $x, y, a, b$ are times in seconds. None of the intervals within $I_1$ ...
user avatar
  • 155
1 vote
0 answers
29 views

Social Networking Disease Transmission

You are given an undirected graph (social network) in which each edge $e = (v, v')$ has an interval $I_e = [l_e, u_e]$ on it. The meaning is that you know that $v$ and $v'$ met at some point during ...
user avatar
3 votes
1 answer
385 views

Maximum interval scheduling - Circular Variation

Consider a variant of interval scheduling except now the intervals are arcs on a circle. The goal is to find the maximum number of arcs that do not overlap. Let $C$ be the circle on the plane centered ...
user avatar
4 votes
0 answers
70 views

Efficient 2d interval merging product

Suppose I have two tables of 2d intervals (axis-aligned rectangles) with values attributed to each interval. ...
user avatar
  • 215
7 votes
0 answers
160 views

Finding a rainbow independent set in a circle

Inside the interval $[0,1]$, there are $n^2$ intervals of $n$ different colors: $n$ intervals of each color. The intervals of each color are pairwise-disjoint. A rainbow independent set is a set of $n$...
user avatar
1 vote
0 answers
24 views

Finding max values at a point given a list of ranges

In coding competitions I usually see problems that involve dealing with values in given ranges. A typical example is, given a list of 3-tuples defined as so ...
user avatar
  • 111
3 votes
1 answer
133 views

Merging Tuples of Intervals

Suppose I have a list of tuples. Each tuple contains 2 intervals. The intervals in each tuple have nothing to do with each other. I would like to find a smaller list of tupels that covers all elements ...
user avatar
  • 53
7 votes
0 answers
91 views

Optimality of DSATUR on interval graphs

The DSATUR algorithm is a greedy graph coloring algorithm. It consists of applying the usual greedy coloring algorithm, considering vertices in reverse lexicographic order of (number of different ...
user avatar
  • 6,942
1 vote
1 answer
249 views

Minimal number of intervals that covers $\{1,...,k\}$

Let $F$ be a family of sets of consecutive integers in $\{1,…,k\}$ that is closed under taking subintervals, i.e. for any $a≤b≤c≤d$, if $\{a,…,d\} \in F$, then $\{b,…,c\} \in F$ also. Find a minimum ...
user avatar
0 votes
1 answer
37 views

What's the name of this packing problem?

I'm trying to pack sets of intervals, to find distinct buckets of intervals. The buckets should not be overlapping. For example if I have these intervals: ...
user avatar
1 vote
1 answer
57 views

Intersection of Decision Tree Boundaries in Higher Dimensions

I have trained two binary decision tree classifiers with splits in $\mathbb{R}^4$. Same data, but from two different patches. Now, I want to find the exact intervals where the two trees disagree. The ...
user avatar
  • 11
2 votes
2 answers
122 views

Data structure for interval subset queries

I have a set $S$ of intervals. I'd like to store them in a data structure, so that I can handle the following query efficiently: given a query interval $q$, count the number of intervals $s \in S$ ...
user avatar
  • 140k
1 vote
1 answer
128 views

Find minimum number of points which intersect overlapping arcs

Say I have a circle of a fixed radius, with overlapping arc intervals along its edge. I want to return a minimum set of Points which intersects all arcs in $n^2$ time. I'm having some trouble proving ...
user avatar
2 votes
1 answer
129 views

How can I implement a data structure which calculates the number of nested intervals in sub-linear time?

Is there a data structure which can maintain a list of intervals and the following operations? ...
user avatar
  • 43
1 vote
1 answer
75 views

What does it mean that a set of intervals is sorted by the right and left endpoints?

While reading a paper (On the k-coloring of intervals), I came upon the following description: "Input: An integer k, and a set of n intervals sorted by right and left endpoints. The intervals are ...
user avatar
2 votes
2 answers
529 views

Algorithm To Compute The Gaps Between A Set of Intervals

Problem Given a set of intervals with possibly non-distinct start and end points, find all maximal gaps. A gap is defined as an interval that does not overlap with any given interval. All endpoints ...
user avatar
  • 123
0 votes
1 answer
142 views

Intervals Collision Detection Algorithm

Given a collection of non-empty intervals [a,b), where a/b are integers in some finite range (ex. 0...100) and a is less than b, can you find an algorithm that will detect all intervals that exhibit ...
user avatar
  • 103
4 votes
1 answer
242 views

How to group intervals which overlap by some amount?

I have an algorithm that generates a list of intervals. The algorithm is run m times. Lets mark the intervals as tuples (s1, e1), (s2, e2), .., (sn, en). It is ...
user avatar
  • 151
1 vote
0 answers
134 views

Is it posssible to calculate the intersection area of rectangles with sweep Line and Interval or Segment Tree

I am curently working on automatic label placement, so for evaluating a model, one metric is to calculate the Area A: A is the sum of every part of a rectangle covered by another. So if two rectangle ...
user avatar
2 votes
1 answer
97 views

Returning random integer from interval based on last result and a seed

Suppose we have an interval of integers [a, b]. I would like to have a function that returns random members from within the interval, without repetitions. Once that all members within the interval are ...
user avatar
1 vote
1 answer
60 views

Is there an Interval Tree which supports O(1) dynamic space requirements for queries?

I observed that all the interval tree implementations I am able to come up with are required to utilize a stack (or a-like) to answer queries (report any overlapping interval with a key). In general ...
user avatar
  • 121
2 votes
1 answer
59 views

Why does a range query on a segment tree return at most $\lceil \log_2{N} \rceil$ nodes?

If an array $A[1 \ldots N]$ is represented using a segment tree having sets in each interval, why does a range query $[L\ldots R]$ returns at most $\lceil \log_2{N} \rceil$ sets (or disjoint intervals)...
user avatar
3 votes
1 answer
58 views

Interval sorting that avoids covering

I have a collection of intervals and I want to sort them so that the order is interpreted as a sort of "z-index". That is, a given interval may or may not be "visible" depending on whether the merge ...
user avatar
2 votes
1 answer
106 views

Schedule X Classes In N Classrooms

I would really appreciate any thought on this, or under which category does this problem fall (Interval scheduling, Interval partitioning,...) I am really out of thoughts I have X number of classes ...
user avatar
  • 21
2 votes
2 answers
534 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. ...
user avatar
  • 364
9 votes
1 answer
342 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{...
user avatar
  • 364
2 votes
1 answer
77 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 ...
user avatar
  • 364
3 votes
1 answer
54 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 ...
user avatar
2 votes
1 answer
60 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 ...
user avatar
3 votes
1 answer
108 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]]...
user avatar
  • 177
0 votes
0 answers
261 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 ...
user avatar
0 votes
2 answers
275 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 ...
user avatar
3 votes
2 answers
375 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 ...
user avatar
  • 85
3 votes
0 answers
204 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, ...
user avatar
1 vote
1 answer
533 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 ...
user avatar
  • 317
2 votes
1 answer
555 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 ...
user avatar
0 votes
1 answer
379 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 ...
user avatar
1 vote
2 answers
260 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 ...
user avatar
1 vote
1 answer
124 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 ...
user avatar
  • 48
2 votes
1 answer
139 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 ...
user avatar
1 vote
0 answers
49 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 (...
user avatar
  • 11
0 votes
2 answers
53 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 ...
user avatar
  • 103
1 vote
0 answers
47 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 ...
user avatar