Greedy.java

amitsen01ei

Oct 2nd, 2023

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

Java 1.72 KB | Source Code | 0 0

raw download clone embed print report

import java.util.ArrayList;
public class Greedy {
/**
* Given a set of intervals, finds the length of the maximal set of mutually
* disjoint intervals. Two intervals are considered disjoint if they don't
* have any point in common.
*
* <p>Time complexity: O(N * log(N)) where N is the number of intervals.
* This is because the main computational effort is spent on sorting the intervals.
* After sorting, the algorithm performs a single pass through the list.
*
* <p>Space complexity: O(1) as no additional space (proportional to the input size)
* is used beyond the input list of intervals. However, the sorting itself in Java
* might require O(N) space due to the characteristics of the sorting algorithm
* employed by the Arrays.sort() method in the List interface that uses Tim Sort.
*
* @param matrix The list of intervals, where each interval is represented as a list with
* two integers denoting the start and end of the interval.
* @return The length of the maximal set of mutually disjoint intervals.
*
*/
public static int maxDisjointIntervals(ArrayList<ArrayList<Integer>> matrix) {
matrix.sort(Greedy::comparing);
var count = 1;
var lastEnd = matrix.get(0).get(1);
for (var r : matrix) {
if (r.get(0) > lastEnd) {
count++;
lastEnd = r.get(1);
}
}
return count;
}
private static int comparing(ArrayList<Integer> a, ArrayList<Integer> b) {
return a.get(1).equals(b.get(1)) ? Integer.compare(a.get(0), b.get(0)) :
Integer.compare(a.get(1), b.get(1));
}
}

Add Comment

Please, Sign In to add comment