# Tag Info

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

3

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.

2

This is precisely the graph coloring problem. Each subset of $C$ is a color, and we are trying to prevent adjacent vertices from having the same color, while minimizing the number of colors used. According to these lecture notes there is a polynomial-time greedy algorithm for coloring interval graphs based on the fact that every interval graph has a perfect ...

2

@Tassle algorithm works great but needs more explaining for vectors ordering. To do so, put all your starting and ending times in a vector and sort them in increasing order, breaking ties by putting end-times before start-times. Set a counter = 0 and an empty unordered set S. Now go through your vector of times in order. The priority for the first ...

2

I suppose you want to delete as little EmptyEvents as possible. In that case, you can achieve what you want in O(nlog(n)) time, where n is the number of events. Proceed as follows: First, get rid of the EmptyEvents which overlap with a NormalEvent. To do so, put all your starting and ending times in a vector and sort them in increasing order, breaking ...

1

Here's the basic idea. Let a dyadic interval be an interval of the form $$[2^b a,2^b(a+1)-1]$$ for some integer $a,b \geq 0$. Claim 1. If $m < 2^n$ then any interval of the form $[0,m-1]$ can be written as the disjoint union of at most $n$ dyadic intervals. Proof. Expand $m$ as a sum of decreasing powers of 2: $$m = 2^{a_1} + \cdots + 2^{a_k}.$$ ...

1

If no two intervals end at the same point then you can simply sort them in increasing order of their right endpoint, and all of them will be visible. If more than two intervals can end at the same point, then sort the intervals $[a,b]$ in increasing order of $b$ and break ties in decreasing order of $a$. Assume w.l.o.g., that there are no identical ...

1

Interval graphs are chordal graphs, so you can use a linear time algorithm for finding max clique in a chordal graph. This can be done by first finding a perfect elimination ordering, and then using the fact that every time a vertex is eliminated it forms a clique together with its neighbors that are not eliminated yet. Furthermore all maximal cliques appear ...

1

I'm assuming that $W$ is an integer upper bound to $\sum_i w_i$, as asked by xskxzr, that all $w_i$ are positive integers, and that the values $w$ in the queries are also integers upper bounded by $W$. For $i \ge 1$, let $S[i,w]$ be the largest index $j \in \{1, \dots, i\}$ such that it is possible to select a subset of $\{w_k : j \le k \le i \}$ of weight ...

1

First, suppose the intervals $[l_1,r_1],\ldots,[l_n,r_n]$ are pairwise intersecting, then we have $l_i\le r_j$ for any $i,j$, which means for any $i$, $l_i\le\max_k l_k\le r_k$, i.e. all these intervals contain the point $\max_k l_k$. The observation above leads to the algorithm mentioned in jaxa 9831's answer: First, sort the intervals according to ...

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