Java 从父时间范围中减去时间范围数组

Question

时间范围（表示视频长度）采用这种格式的字符串：HH:mm:ss。假设我有一个父时间范围，如下所示：00:00:59 代表一个 59 秒长的视频。

我现在有一组时间范围对，我必须从视频中删除，因为在这些时间范围内视频中没有发生任何有趣的事情。例如输入数组：

[
00:00:10 to 00:00:20, 
00:00:30 to 00:00:35, 
00:00:35 to 00:00:40
]

我希望从 59 秒的视频中删除这些不重要的范围，并计算剩余的有效视频片段。在上述情况下，理想的输出将是：

[
00:00:00 to 00:00:10, 
00:00:20 to 00:00:30, 
00:00:40 to 00:00:59
]

Answer 1

排序、迭代和包含

按开始时间对输入区间进行排序（排除）
迭代要排除的每个输入区间
包括上一个排除区间结束与当前排除区间开始之间的任何区间
最后，通过与总长度比较来检查是否有剩余间隔

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class SequenceTest {

    public static void main(String[] args) {
        final SequenceTest sequenceTest = new SequenceTest();
        sequenceTest.computeIncludeIntervals(59,
            Arrays.asList((new int[][]{{10, 20}, {30, 35}, {35, 40}})));
        sequenceTest.computeIncludeIntervals(40,
            Arrays.asList((new int[][]{{10, 20}, {30, 35}, {35, 40}})));
        sequenceTest.computeIncludeIntervals(41,
            Arrays.asList((new int[][]{{10, 20}, {30, 35}, {35, 40}})));
        sequenceTest.computeIncludeIntervals(41,
            Arrays.asList((new int[][]{{0, 20}, {30, 35}, {36, 40}})));

    }

    protected List<int[]> computeIncludeIntervals(final int totalLength, List<int[]> excludeIntervals) {
        // sort the sequence by start time - O(NlogN)
        excludeIntervals.sort((a, b) -> a[0] == b[0] ? Integer.compare(a[1], b[1])
            : Integer.compare(a[0], b[0]));

        int previousEnd = 0; // initial state
        final List<int[]> result = new ArrayList<>();
        for (int[] exclude : excludeIntervals) {
            if (previousEnd < exclude[0]) {
                int[] include = new int[]{previousEnd, exclude[0]};
                result.add(include);
            }
            previousEnd = Math.max(previousEnd, exclude[1]);
        }

        // remaining tail
        if (previousEnd < totalLength) {
            result.add(new int[]{previousEnd, totalLength});
        }

        System.out.println("Total Length: " + totalLength + ", Input: " + excludeIntervals.stream()
            .map(interval -> interval[0] + ":" + interval[1])
            .collect(Collectors.joining(", ")));
        System.out.println("Included: " + result.stream().map(interval -> interval[0] + ":" + interval[1])
            .collect(Collectors.joining(", ")));

        return result;
    }
}

实际解决方案

编写转换器将输入日期时间转换为新纪元 unix 时间
使用上述方法计算包含间隔
转换包括使用反向转换器的纪元时间到日期时间的间隔

Answer 2

我写了 2 类：TimeRange 和 TimeRangeSet。

用法：

public static void main(String[] args) throws ParseException
{
    TimeRange minuend = new TimeRange("00:00:00", "00:00:59");
    
    TimeRangeSet subtrahendSet = new TimeRangeSet();
    
    subtrahendSet
        .addRange("00:00:10", "00:00:20")
        .addRange("00:00:30", "00:00:35")
        .addRange("00:00:35", "00:00:40");
        
    TimeRangeSet differenceSet = minuend.minus(subtrahendSet);
    
    System.out.println("\t " + minuend);
    System.out.println("minus\t" + subtrahendSet);
    System.out.println("equals\t" + differenceSet);
}

输出：

         00:00:00 to 00:00:59
minus   [00:00:10 to 00:00:20, 00:00:30 to 00:00:35, 00:00:35 to 00:00:40]
equals  [00:00:00 to 00:00:10, 00:00:20 to 00:00:30, 00:00:40 to 00:00:59]

时间范围：

import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.time.temporal.ValueRange;

public class TimeRange implements Comparable <TimeRange>
{
    private ValueRange valueRange;
    
    private static final SimpleDateFormat simpleDateFormat = new SimpleDateFormat("HH:mm:ss");
            
    public TimeRange(ValueRange valueRange)
    {
        this.valueRange = valueRange;
    }
    
    public TimeRange(String fromTime, String toTime) throws ParseException
    {
        this
        (
            ValueRange.of(simpleDateFormat.parse(fromTime).getTime(), simpleDateFormat.parse(toTime).getTime())
        );
    }
    
    public TimeRangeSet minus(TimeRangeSet subtrahendSet)
    {
        TimeRangeSet difference = new TimeRangeSet();
        
        subtrahendSet.forEach
        (
            (subtrahend) ->
            {
                TimeRangeSet subDifference = new TimeRangeSet();
                subDifference.addAll(minus(subtrahend));
                difference.addAll(subDifference.minus(subtrahendSet));
            }
        );
        
        return difference;
    }
        
    public TimeRangeSet minus(TimeRange subtrahend)
    {
        TimeRangeSet difference = new TimeRangeSet();
        
        long A  = valueRange.getMinimum();
        long B  = valueRange.getMaximum();
        long C  = subtrahend.valueRange.getMinimum();
        long D  = subtrahend.valueRange.getMaximum();
        
                
        if ( B <= C )                                       //  A-----------B
            difference.addRange(ValueRange.of(A, B));       //              C-------D
        else
            
        if ( A >= D )                                       //          A-----------B
            difference.addRange(ValueRange.of(A, B));       //  C-------D
        else
            
        if ( (A >= C)  && (A < D) && (B > D) )              //  A---------------B
            difference.addRange(ValueRange.of(D, B));       //  C-------D                                               
        else
            
        if ( (A < C)  && (B > C) && (B <= D) )              //  A---------------B
            difference.addRange(ValueRange.of(A, C));       //          C-------D                   
        else
            
        if ( (A < C)  && (B > C) && (B > D) )               //  A---------------B
        {                                                   //      C-------D
            difference.addRange(ValueRange.of(A, C));
            difference.addRange(ValueRange.of(D, B));
        }
        
        return difference;
    }
    
    public String toString()
    {
        return String.format("%tT to %tT", valueRange.getMinimum(), valueRange.getMaximum());
    }
    
    
    @Override
    public int compareTo(TimeRange input)
    {
        return this.toString().compareTo(input.toString());
    }
}

TimeRangeSet:

import java.text.ParseException;
import java.time.temporal.ValueRange;
import java.util.TreeSet;


public class TimeRangeSet extends TreeSet <TimeRange>
{
    private static final long serialVersionUID = 1L;

    public TimeRangeSet addRange(ValueRange valueRange)
    {
        super.add(new TimeRange(valueRange));
        return this;
    }
    
    public TimeRangeSet addRange(String fromTime, String toTime) throws ParseException
    {
        super.add(new TimeRange(fromTime, toTime));
        return this;
    }
    
    public TimeRangeSet minus(TimeRangeSet subtrahendSet)
    {       
        subtrahendSet.forEach
        (
            (subtrahend) ->
                ((TimeRangeSet) this.clone()).forEach
                (
                    (minuend) ->
                    {
                        if (this.addAll(minuend.minus(subtrahend)))
                            this.remove(minuend);
                    }
                )
        );
        
        return this;
    }
}

Java 从父时间范围中减去时间范围数组

Java subtract array of time ranges from a parent time range

java-time

排序、迭代和包含

实际解决方案