Questions tagged [intervals]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer
37 views

Dynamic Programming problem about intervals

This is algorithms and data structures assignment and I have been thinking 3 days about it. You are given N sections, placed on numeric axis. Numeric axis is divided by unit intervals. Each section in ...
guitarMan's user avatar
0 votes
0 answers
19 views

Intervals with costs and limited resources, dynamic programming

I have been trying to solve the following problem. I have n intervals each with a cost.I want to choose a subset of the intervals that maximizes the cost but with the following constraint. Each ...
SotirisD's user avatar
1 vote
0 answers
93 views

complexity of graph matching with order constraint

Given a graph with $n$ vertices and $m$ edges, $m \le {n \choose 2}$, we index the vertices from 1 to $n$, and denote every edge by $(l,r)$ where $1\le l < r \le n$. Find the maximum $k$ such that ...
quTANum's user avatar
  • 11
-1 votes
2 answers
64 views

Given m intervals and an array of integers, your task is to minimize the number of operations in which you can make the elements of the array nonposit

You are given the number $m$ and $m$ intervals of the form $a_i, b_i, v_i$, where $a_i<=b_i$ and $v_i>0$ and also a number $n$ and an array $s$ of length $n$, where $s_i>0$. In one operation ...
John's user avatar
  • 1
0 votes
1 answer
27 views

Is minimum interval hitting problem NP-HARD?

Consider this problem: We want to mark some integer numbers such that we mark the minimum number of the numbers and satisfy some constraints. Each constraint wants that at least $k$ numbers in ...
Soroush Vahidi's user avatar
0 votes
1 answer
203 views

Proving the correctness of a greedy algorithm for the Circular Scheduling Problem

Consider the following variation on the Interval Scheduling Problem You have a processor that can operate 24 hours a day, every day. People submit requests to run daily jobs on the processor. Each ...
Tejas Anand's user avatar
2 votes
2 answers
610 views

Select a subset of k intervals which form maximum length if we take union of these k intervals

Suppose we have $n$ intervals given in the form of (startTime,EndTime). I wish to calculate maximum length of the region that is exactly union of $1<=k<=n$ intervals. Note that there are 2 cases ...
Kitwradr's user avatar
  • 123
1 vote
1 answer
99 views

pairing numbers and intervals

subject: pairing numbers and intervals Let NUMBERS be a list of n integer numbers. The numbers are listed in no specific order. ...
JohnHernandez's user avatar
7 votes
2 answers
216 views

Choose non-adjacent numbers from intervals

Given a list of intervals with integral endpoints, we want to find out if we can choose one integer from each interval so that no two chosen numbers are adjacent. Can we do this in polynomial time? My ...
simmons's user avatar
  • 131
0 votes
0 answers
89 views

Using Hashing to count the number of occurrences of a pattern within an integer array

So I have a problem that is ,I have an integer array and first I define an interval as a good interval iff, within the interval every integer appears an even (including zero) number of times. I want ...
ISeekTheWisdom's user avatar
0 votes
0 answers
146 views

Weighted interval scheduling, exponential time/ NP-complete?

According to this, a weighted schedule is considered NP-complete (not solve-able in polynomial time) if it has groups of 3 or more intervals: https://en.wikipedia.org/wiki/Interval_scheduling#NP-...
Tyler's user avatar
  • 11
0 votes
3 answers
2k views

Greedy algorithm for postive interval covering

Consider the following problem from Jeff Erickson: Algorithms that also appears in this post, which wants us to prove a lower bound for the problem. Suppose you are given an array $A[1 .. n]$ of ...
ErroR's user avatar
  • 267
1 vote
0 answers
26 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: ...
Alexandr Dorofeev's user avatar
3 votes
1 answer
396 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 ...
NiRvanA's user avatar
  • 159
1 vote
2 answers
114 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 ...
chrylis -cautiouslyoptimistic-'s user avatar
3 votes
1 answer
82 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 ...
worldsmithhelper's user avatar
1 vote
1 answer
234 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. ...
Vectorizer's user avatar
1 vote
0 answers
55 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 ...
Th F's user avatar
  • 11
0 votes
1 answer
470 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 ...
Dincio's user avatar
  • 111
3 votes
1 answer
92 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$ ...
Sid's user avatar
  • 165
1 vote
0 answers
32 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 ...
IUissopretty's user avatar
3 votes
1 answer
941 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 ...
AspiringMat's user avatar
4 votes
0 answers
116 views

Efficient 2d interval merging product

Suppose I have two tables of 2d intervals (axis-aligned rectangles) with values attributed to each interval. ...
yupbank's user avatar
  • 215
7 votes
0 answers
166 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$...
Erel Segal-Halevi's user avatar
1 vote
0 answers
27 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 ...
nick2225's user avatar
  • 111
3 votes
1 answer
171 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 ...
df21's user avatar
  • 63
8 votes
1 answer
389 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 ...
Nathaniel's user avatar
  • 12.5k
1 vote
1 answer
1k 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 ...
Karambit's user avatar
0 votes
1 answer
41 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: ...
Luca Spiller's user avatar
1 vote
1 answer
113 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 ...
Nate S.'s user avatar
  • 11
2 votes
2 answers
391 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$ ...
D.W.'s user avatar
  • 156k
1 vote
1 answer
247 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 ...
Elliott de Launay's user avatar
2 votes
1 answer
242 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? ...
pblpbl's user avatar
  • 43
1 vote
1 answer
185 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 ...
Sebastian Allard's user avatar
2 votes
2 answers
1k 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 ...
Mojo's user avatar
  • 123
0 votes
1 answer
301 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 ...
andrewz's user avatar
  • 103
4 votes
1 answer
353 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 ...
mibm's user avatar
  • 149
1 vote
0 answers
177 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 ...
ThundeRat's user avatar
2 votes
1 answer
119 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 ...
sn0wtroopeer's user avatar
0 votes
1 answer
105 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 ...
milck's user avatar
  • 111
2 votes
1 answer
76 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)...
DoubtExpert's user avatar
3 votes
1 answer
80 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 ...
user119447's user avatar
2 votes
1 answer
175 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 ...
cena1's user avatar
  • 21
2 votes
2 answers
972 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. ...
taktoa's user avatar
  • 364
9 votes
1 answer
433 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{...
taktoa's user avatar
  • 364
2 votes
1 answer
86 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 ...
taktoa's user avatar
  • 364
3 votes
1 answer
69 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 ...
dysonsfrog's user avatar
2 votes
1 answer
63 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 ...
greedoid228's user avatar
3 votes
1 answer
170 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]]...
Raito's user avatar
  • 177
0 votes
0 answers
335 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 ...
Raafat Abualazm's user avatar