两个不重叠间隔之间的最大距离

Question

Number of intervals 3

Interval 1 : 1 2

Interval 2: 3 5

Interval 3: 6 7

import java.util.*;
 class Checker implements Comparator<ArrayList>{
        public int compare(ArrayList a, ArrayList b){
          int x = (Integer)a.get(0);
          int y = (Integer)b.get(0);
          return x-y;
        }
    }
class OverlappingIntervals {
   
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        ArrayList<ArrayList<Integer>> intervals = new ArrayList<ArrayList<Integer>>(n);

        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            intervals.add(new ArrayList<Integer>(Arrays.asList(x, y)));
        }

        int result = overlappingIntervals(n, intervals);

        System.out.println(result);
    }

    static int overlappingIntervals(int n, ArrayList<ArrayList<Integer>> intervals) {
        // System.out.println(intervals);
        Checker check = new Checker();

        Collections.sort(intervals, check);
        int ans = -1;
   
        for(int i = 0; i < n-1;i++){
            for(int j = i+1; j < n;j++){
                int x = (Integer)intervals.get(j).get(0)- intervals.get(i).get(1);
                if(x >= 0){     
                    if(x > ans)
                    ans = Math.max(x,ans);
                }                    
            }
        }
        return ans;            
    }        
}

1<=N<=10^5    
1<=l<=r<=10^6

l和r分别是区间的起点和终点。

Answer 1

我们可以在O(n)+O(n*log(n))时间和O(n)空间复杂度下使用stack轻松地解决这一问题。这里的思想是合并间隔，然后检查连续间隔之间的对应间隙。

这里有一个简单而经典的方法来解决您的问题，并举例说明：

import java.util.*;
class OverlappingIntervals
{
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        //int n = sc.nextInt();
        ArrayList<Interval> intervals = new ArrayList<>();

        intervals.add(new Interval(5, 14));intervals.add(new Interval(6, 9));
        intervals.add(new Interval(8, 17));intervals.add(new Interval(23, 25));
        intervals.add(new Interval(36, 56));intervals.add(new Interval(33, 45));
        intervals.add(new Interval(42, 67));intervals.add(new Interval(50, 69));
        intervals.add(new Interval(81, 95));intervals.add(new Interval(99, 111));

        int result = overlappingIntervals(intervals);
        System.out.println(result); // 82 b/w [5 , 17] & [99 , 111]
    }

    static int overlappingIntervals(ArrayList<Interval> intervals)
    {
        // Sorting all Intervals based on there `start` time
        Collections.sort(intervals, Comparator.comparingInt(a -> a.begin));
        int maxDistance = -1;
        
        Stack<Interval> stack = new Stack<>();
        for (Interval currInterval : intervals)
        {
            // Pushing a non-overlapping Interval
            if (stack.empty() || stack.peek().end < currInterval.begin)
                stack.push(currInterval);
            
            // Merging an overlapping Interval
            if (stack.peek().end < currInterval.end)
                    stack.peek().end = currInterval.end;
        }
        /* Now, Stack will have following merged Intervals:
           [5 , 17] <6> [23 , 25] <8> [33 , 69] <12> [81 , 95] <4> [99 , 111] */

        // Checking the gap b/w consecutive Merged-Intervals :
        Interval rightEnd = stack.pop();
        if (stack.empty()) return -1;
        Interval leftEnd = rightEnd;
        while (!stack.empty())
            leftEnd = stack.pop();
        maxDistance = rightEnd.begin - leftEnd.end;
        return maxDistance;
    }        
}
class Interval
{
    int begin, end;
    Interval(int begin, int end)
    {
        this.begin = begin; this.end = end;
    }
    @Override
    public String toString()
    { return "[" +begin+ " , " +end+ "]"; }
}

/** [5========17]   [23=25]  [33=================================69]        [81===========95]   [99======111]
 *  5-------14      23---25      36-----------------56                      81------------95
 *   6---9                            42----------------------67                                 99------111
 *      8------17             33----------45   50----------------69                                      */

我们甚至可以在不合并间隔的情况下这样做，但我相信这种方法更容易理解。有任何疑问请随时询问。