Programmiererforum

from typing import List, Tuple
from dataclasses import dataclass

Interval = Tuple[float, float]  # Single interval with (min, max) bounds
Range = List[Interval]          # Multi-dimensional range

@dataclass
class Overlap:
range1_index: int                      # Index of the first range in the list
range2_index: int                      # Index of the second range in the list
overlapping_intervals: List[Interval]  # Overlapping intervals for each dimension

def find_overlapping_ranges(ranges: List[Range]) -> List[Overlap]

def find_overlapping_ranges(ranges: List[Range]) -> bool

Angenommen, ich schreibe die Funktion find_overlapping_ranges, um überlappende Bereiche in einer Liste mehrdimensionaler Bereiche zu finden.
[code]from typing import List, Tuple
from dataclasses import dataclass

Interval = Tuple[float, float] # Single interval with (min, max) bounds
Range = List[Interval] # Multi-dimensional range

@dataclass
class Overlap:
range1_index: int # Index of the first range in the list
range2_index: int # Index of the second range in the list
overlapping_intervals: List[Interval] # Overlapping intervals for each dimension

def find_overlapping_ranges(ranges: List[Range]) -> List[Overlap]

[/code]
Die erwartete Anzahl von Bereichen beträgt ~10.000 und die erwartete Anzahl von Dimensionen beträgt ~100. Vielleicht ist es erwähnenswert, dass in den meisten Fällen keine Überlappung erwartet wird und die Funktion [] zurückgeben sollte. Der naive Ansatz, jedes Bereichspaar zu überprüfen, scheint nicht machbar. Welchen Algorithmus würden Sie vorschlagen?
Wenn kein Algorithmus machbar ist, würde ich eine einfachere Funktion has_overlap verwenden, um zu prüfen, ob es eine Überlappung gibt.
[code]def find_overlapping_ranges(ranges: List[Range]) -> bool
[/code]