Untitled
unknown
plain_text
a month ago
2.9 kB
6
Indexable
Never
import java.util.*; public class MinimumConnectedSets { public static void main(String[] args) { List<Integer> a = Arrays.asList(3, 2, 3); List<Integer> b = Arrays.asList(5,9,3); int k = 10; int result = minimumDivision(a, b, k); System.out.println("Minimum connected sets: " + result); // Expected output: 2 } public static int minimumDivision(List<Integer> a, List<Integer> b, int k) { int n = a.size(); List<int[]> intervals = new ArrayList<>(); // Combine a and b into intervals for (int i = 0; i < n; i++) { intervals.add(new int[]{a.get(i), b.get(i)}); } // Sort intervals by the start value intervals.sort(Comparator.comparingInt(interval -> interval[0])); int originalConnectedSets = countConnectedSets(intervals); int minConnectedSets = originalConnectedSets; // Try inserting the segment between every possible pair of intervals for (int i = 0; i <= n; i++) { int[] newInterval; if (i == 0) { // Insert segment before the first interval newInterval = new int[]{intervals.get(0)[0] - k, intervals.get(0)[0]}; } else if (i == n) { // Insert segment after the last interval newInterval = new int[]{intervals.get(n - 1)[1], intervals.get(n - 1)[1] + k}; } else { // Insert segment between intervals[i-1] and intervals[i] int start = intervals.get(i - 1)[1]; int end = intervals.get(i)[0]; newInterval = new int[]{start, start + k}; // Ensure that the new interval does not overlap the next one if (newInterval[1] > end) { newInterval[1] = end; } } // Simulate inserting the new interval List<int[]> newIntervals = new ArrayList<>(intervals); newIntervals.add(newInterval); newIntervals.sort(Comparator.comparingInt(interval -> interval[0])); // Count the connected sets with the new interval inserted int connectedSets = countConnectedSets(newIntervals); minConnectedSets = Math.min(minConnectedSets, connectedSets); } return minConnectedSets; } private static int countConnectedSets(List<int[]> intervals) { int connectedSets = 1; int currentEnd = intervals.get(0)[1]; for (int i = 1; i < intervals.size(); i++) { int[] current = intervals.get(i); if (current[0] > currentEnd) { connectedSets++; currentEnd = current[1]; } else { currentEnd = Math.max(currentEnd, current[1]); } } return connectedSets; } }
Leave a Comment