fork(4) download
copy 
  1. import java.util.Arrays;
  2. import java.util.Comparator;
  3.  
  4. class Interval {
  5. 	int start;
  6. 	int end;
  7.  
  8. 	public Interval(int start, int end) {
  9. 		this.start = start;
  10. 		this.end = end;
  11. 	}
  12. }
  13.  
  14. class MyComparator implements Comparator<Interval> {
  15. 	public int compare(Interval a, Interval b) {
  16. 		return b.start - a. start;
  17. 	}
  18. }
  19.  
  20. class MergeOverlappingIntervals {
  21.  
  22. 	static int max(int a, int b) {
  23. 		return (a>b)?a:b;
  24. 	}
  25.  
  26. 	static int min(int a, int b) {
  27. 		return (a<b)?a:b;
  28. 	}
  29.  
  30. 	static void mergeOverlappingIntervals(Interval[] arr) {
  31.  
  32. 		int n = arr.length;
  33.  
  34. 		Arrays.sort(arr,new MyComparator());
  35.  
  36. 		int index = 0;
  37. 		for(int i=0;i<n;i++) {
  38. 			if(index != 0 && arr[i].end >= arr[index-1].start) {
  39. 				while(index != 0 && arr[i].end >= arr[index-1].start) {
  40. 					arr[index-1].start =  min(arr[index-1].start,arr[i].start);
  41. 					arr[index-1].end = max(arr[index-1].end,arr[i].end);
  42. 					index--;
  43. 				}
  44. 			}
  45. 			else
  46. 				arr[index] = arr[i];
  47. 			index++;
  48. 		}
  49.  
  50. 		for(int i=0;i<index;i++)
  51. 			System.out.print("[" + arr[i].start + ", " + arr[i].end + "], ");
  52. 		System.out.println();		
  53.  
  54. 	}
  55.  
  56. 	static void printArray(Interval[] arr) {
  57. 		for(int i=0;i<arr.length;i++)
  58. 			System.out.print("[" + arr[i].start + ", " + arr[i].end + "], ");
  59. 		System.out.println();
  60. 	}
  61.  
  62. 	public static void main(String[] args) {
  63. 		Interval[] arr = {new Interval(1,3),new Interval(2,4),new Interval(5,7), new Interval(6,8)};
  64.  
  65. 		printArray(arr);
  66.  
  67. 		mergeOverlappingIntervals(arr);
  68. 	}
  69. }
Success #stdin #stdout 0.1s 320512KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[1, 3], [2, 4], [5, 7], [6, 8], 
[5, 8], [1, 4],
https://ideone.com/ioH2YW
language:
Java (12.0.1)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!