Advertisement
Guest User

Untitled

a guest
Oct 1st, 2017
119
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.34 KB | None | 0 0
  1. import java.util.Arrays;
  2. import java.util.Scanner;
  3.  
  4. public class Pr06OverlappingIntervals {
  5.  
  6.     public static void main(String[] args) {
  7.         Scanner scanner = new Scanner(System.in);
  8.  
  9.         int intervalsCount = Integer.parseInt(scanner.nextLine());
  10.  
  11.         int[] start = new int[intervalsCount];
  12.         int[] end = new int[intervalsCount];
  13.  
  14.         for (int i = 0; i < intervalsCount; i++) {
  15.             int[] currentInterval = Arrays.stream(scanner.nextLine().split(","))
  16.                     .mapToInt(Integer::parseInt).toArray();
  17.             start[i] = currentInterval[0];
  18.             end[i] = currentInterval[1];
  19.         }
  20.         // Algorithm: http://www.zrzahid.com/maximum-number-of-overlapping-intervals/
  21.         Arrays.sort(start);
  22.         Arrays.sort(end);
  23.  
  24.         int currentOverlap = 0;
  25.         int i = 0;
  26.         int j = 0;
  27.         boolean overlappingIntervals = false;
  28.  
  29.         while (i < intervalsCount && j < intervalsCount) {
  30.             if (start[i] <= end[j]) {
  31.                 currentOverlap++;
  32.                 i++;
  33.             } else {
  34.                 currentOverlap--;
  35.                 j++;
  36.             }
  37.  
  38.             if (currentOverlap > 1) {
  39.                 overlappingIntervals = true;
  40.                 break;
  41.             }
  42.         }
  43.  
  44.         System.out.println(overlappingIntervals);
  45.     }
  46. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement