Skip to main content
MathOverflow

Return to Question

Fixed spelling and grammar of title
Link
MTS
MTS
  • 8.6k
  • 2
  • 35
  • 65

How to get the largest Subsetsubset of a Setset of Set'ssets of Intervallsintervals with no overlapping Intervallsintervals

edited body
Source Link
Nick Russler
Nick Russler
  • 41
  • 1
  • 5

Given: Set of Set of Intervals. Example {{[1(1,2]2), [3(3,4]4)}, {[1(1, 3]3)}, {[13(13,14]14)}}

Wanted Result: Largest Subset, in which no Interval overlaps with another from every Set pairwise.

Example:

Input {{[1(1,2]2), [3(3,4]4)}, {[1(1, 3]3)}, {[13(13,14]14)}}

A possible Solution would be: {{[1(1,2]2), [3(3,4]4)}, {[13(13,14]14)}}

Another could be {{[1(1, 3]3)}, {[13(13,14]14)}},
it's not important that the solution above has more 'subelements',
its only important that 2 = |{{[1(1,2]2), [3(3,4]4)}, {[13(13,14]14)}}| = |{{[1(1, 3]3)}, {[13(13,14]14)}}|

Now i am looking for a good/efficient Algorithm to solve that problem.

Given: Set of Set of Intervals. Example {{[1,2], [3,4]}, {[1, 3]}, {[13,14]}}

Wanted Result: Largest Subset, in which no Interval overlaps with another from every Set pairwise.

Example:

Input {{[1,2], [3,4]}, {[1, 3]}, {[13,14]}}

A possible Solution would be: {{[1,2], [3,4]}, {[13,14]}}

Another could be {{[1, 3]}, {[13,14]}},
it's not important that the solution above has more 'subelements',
its only important that 2 = |{{[1,2], [3,4]}, {[13,14]}}| = |{{[1, 3]}, {[13,14]}}|

Now i am looking for a good/efficient Algorithm to solve that problem.

Given: Set of Set of Intervals. Example {{(1,2), (3,4)}, {(1, 3)}, {(13,14)}}

Wanted Result: Largest Subset, in which no Interval overlaps with another from every Set pairwise.

Example:

Input {{(1,2), (3,4)}, {(1, 3)}, {(13,14)}}

A possible Solution would be: {{(1,2), (3,4)}, {(13,14)}}

Another could be {{(1, 3)}, {(13,14)}},
it's not important that the solution above has more 'subelements',
its only important that 2 = |{{(1,2), (3,4)}, {(13,14)}}| = |{{(1, 3)}, {(13,14)}}|

Now i am looking for a good/efficient Algorithm to solve that problem.

deleted 13 characters in body; edited title; edited body
Source Link
Nick Russler
Nick Russler
  • 41
  • 1
  • 5

How to get the largest Subset of a Set of Set's of IntegersIntervalls with minimum difference of each elementno overlapping Intervalls

I have aGiven: Set of Set'sSet of Integers For example:Intervals. Example {{1[1,32], [3,4]}, {5[1,7 3]}, {2,10[13,1614]}}

Now i want the largest (in terms of elements) subset of Sets that only contains Set'sWanted Result: Largest Subset, in which each element has a minimal difference (pairwise) to each other elementno Interval overlaps with another from all set'severy Set pairwise.

for example with the set {{1,3}, {5,7}, {2,10, 16}} and the minimum difference 2 an possible solution would beExample:

{{1,3}, {5,7}}

because 1,3,5 and 7 have a minimal distance to all elements (excluding itself). The third Set {2,10} ist not chosen because 2 has not enough distance to 1.


Input {{[1,2], [3,4]}, {[1, 3]}, {[13,14]}}

A possible Solution would be: {{[1,2], [3,4]}, {[13,14]}}

Another could be {{[1, 3]}, {[13,14]}},
it's not important that the solution above has more 'subelements',
its only important that 2 = |{{[1,2], [3,4]}, {[13,14]}}| = |{{[1, 3]}, {[13,14]}}|

Is thereNow i am looking for a know algorithmgood/methodefficient Algorithm to dosolve that ?problem.

How to get the largest Set of Set's of Integers with minimum difference of each element

I have a Set of Set's of Integers For example: {{1,3}, {5,7}, {2,10,16}}

Now i want the largest (in terms of elements) subset of Sets that only contains Set's in which each element has a minimal difference (pairwise) to each other element from all set's

for example with the set {{1,3}, {5,7}, {2,10, 16}} and the minimum difference 2 an possible solution would be:

{{1,3}, {5,7}}

because 1,3,5 and 7 have a minimal distance to all elements (excluding itself). The third Set {2,10} ist not chosen because 2 has not enough distance to 1.

Is there a know algorithm/method to do that ?

How to get the largest Subset of a Set of Set's of Intervalls with no overlapping Intervalls

Given: Set of Set of Intervals. Example {{[1,2], [3,4]}, {[1, 3]}, {[13,14]}}

Wanted Result: Largest Subset, in which no Interval overlaps with another from every Set pairwise.

Example:


Input {{[1,2], [3,4]}, {[1, 3]}, {[13,14]}}

A possible Solution would be: {{[1,2], [3,4]}, {[13,14]}}

Another could be {{[1, 3]}, {[13,14]}},
it's not important that the solution above has more 'subelements',
its only important that 2 = |{{[1,2], [3,4]}, {[13,14]}}| = |{{[1, 3]}, {[13,14]}}|

Now i am looking for a good/efficient Algorithm to solve that problem.

Source Link
Nick Russler
Nick Russler
  • 41
  • 1
  • 5