인접 시퀀스의 최소 그룹

다이어그램에 가장 잘 설명되어있는 다음과 같은 문제점이 있습니다. 다음 시퀀스를 고려하십시오 (숫자, 날짜 (경우에 따라 날짜) 등)인접 시퀀스의 최소 그룹

diagram

나는 즉, 가능한 가장 긴 시퀀스를 포함하는 그룹의 최소 금액 후자의 예에서 출력과 같은 가장 긴 연속 시퀀스의 모든 그룹을 발견하고 싶습니다.

필자는 일종의 정렬/정렬 (최소/최대 값은 빈 간격을 가질 수 있으므로 여기서는별로 도움이되지 않는 것처럼 보임)을 생각했다. 처음에는 왼쪽으로, 그 다음에는 오른쪽으로, 그러나 나는 그것에 대해서도 확실하지 않습니다.

출처

2013-07-31 Nir

데이터는 어떻게 저장됩니까? 비 유적으로 그리드를 뒤집어서 목록을 반복하면서 목록에서 특정 일에 일정이 있는지 확인합니다. –

@Joey Gennari - 원하는 데이터를 저장할 수 있습니다. 제 경우에는 두 개의 날짜 목록 인 시작 날짜와 종료 날짜가 있습니다. 나는 그것을 뒤집어 쓰는 것이 도움이 될지 모르겠다. 후자의 다이어그램에서 각 시퀀스가 다른 날짜와 같지 않다는 것을 볼 수 있듯이 나는 거기에 날짜를 겹쳐 놓는다. – Nir

그냥 spit-에이를 설정하는 방법에 대한 힌트를 줄 것이다 지난번에 다음과 같이 코딩 한 의사 코드를 볼링했습니다.

var outputRanges = new List<Range>(); 
foreach (var range in inputRanges) 
{ 
    // Let Range.Touches(Range) define a function that returns true 
    // iff the two ranges overlap at all (that is, A.Start and/or A.End 
    // is between B.Start and B.End) 
    var overlaps = outputRanges.Where(range.Touches).ToList(); 

    // If there are no overlaps, then simply add it to the output 
    if (!overlaps.Any()) 
    { 
     outputRanges.Add(range); 
    } 
    // If there are overlaps, merge them 
    else 
    { 
     outputRanges.RemoveAll(overlaps); 
     overlaps.Add(range); 
     outputRange.Add(new Range() { 
      Start = overlaps.Min(_=>_.Start), 
      End = overlaps.Max(_=>_.End) 
     }); 
    } 
}

출처

2013-07-31 19:23:18

정확한 해결책을 보여줍니다 (mcdowella의 답변과 비슷한 알고리즘 사용). 감사! – Nir

시작점과 끝점을 하나의 정렬 된 순서로 정렬 한 다음 해당 순서대로 처리하여 시작점 수를 뺀 개수의 끝점 수를 유지합니다. 이 카운터가 0으로 떨어지면 완전한 갭이 시작됩니다. 인접한 선이 길이가 0 인 간격으로 분리되어 계산되는지 여부에 따라 연결의 경우 종점 앞이나 뒤에 종점을 정렬 할 수 있습니다.

출처

2013-07-31 19:17:36 mcdowella

@msdowella - 그것은 나의 초기 직감이었다. 접근 방식을 설명해 주셔서 감사합니다 – Nir

나는 C#에서 그것을 없지만 SQL이 정확한 문제를 해결했을까요, 아마도 이것은 당신에게 C#

select Resource_ID, Appointment_date, Min(NewStartTime) Start_Time, MAX(End_Time) End_Time 
into #CleanedBlockTimes 
from 
(
    select *, 
     NewStartTime = Dateadd(mi, v.number, t.Start_Time), 
     NewStartTimeGroup = 
      dateadd(mi, 
        1- DENSE_RANK() over (partition by Resource_ID, Appointment_date order by Dateadd(mi, v.number, t.Start_Time)), 
        Dateadd(mi, v.number, t.Start_Time)) 
    from #BlockTimes t 
    inner join master..spt_values v 
     on v.type='P' and v.number <= DATEDIFF(mi, Start_Time, End_Time) 
) X 
group by Resource_ID, Appointment_date, NewStartTimeGroup 
order by Resource_ID, Appointment_date, Start_Time

출처

2013-07-31 19:20:17

범위의 시작 부분을 정렬하십시오.

목록의 머리글에서 시작하여 끝 시간을 목록의 다음 항목 시작과 비교하십시오. 겹치면 종료 시간을 현재 레코드의 종료 시간과 다음 레코드의 종료 시간의 최대 값으로 바꿉니다. 다음 레코드를 제거하십시오. 반복.

다음 레코드가 겹치지 않고 반복되는 경우.

정렬의 경우 O (n log n), 컴파일의 경우 O (n). 전반적으로, o (n log n).

출처

2013-07-31 21:57:13

인접 시퀀스의 최소 그룹

답변

관련 문제