import java.util.*; class Result { private static final int WEEK = 10080; public static List> findDeployableWindows( String part, List inputCsv) { if ("part1".equals(part)) { return solvePart1(inputCsv); } return solvePart2(inputCsv); } // ------------------------------------------------------------ // PART 1 // ------------------------------------------------------------ private static List> solvePart1(List inputCsv) { List allowed = new ArrayList<>(); List freezes = new ArrayList<>(); for (String row : inputCsv) { String[] values = row.split(","); int start = Integer.parseInt(values[0].trim()); int end = Integer.parseInt(values[1].trim()); String type = values[2].trim(); if ("allowed".equals(type)) { allowed.add(new int[]{start, end}); } else { freezes.add(new int[]{start, end}); } } allowed = mergeIntervals(allowed); freezes = mergeIntervals(freezes); List deployable = subtractIntervals(allowed, freezes); return convertToAnswer(deployable); } // ------------------------------------------------------------ // PART 2 // ------------------------------------------------------------ private static List> solvePart2(List inputCsv) { // First line: // utc_now, lead_time, min_continuous, k String[] config = inputCsv.get(0).split(","); int utcNow = Integer.parseInt(config[0].trim()); int leadTime = Integer.parseInt(config[1].trim()); int minContinuous = Integer.parseInt(config[2].trim()); int k = Integer.parseInt(config[3].trim()); List allowed = new ArrayList<>(); List freezes = new ArrayList<>(); // -------------------------------------------------------- // Convert every LOCAL weekly interval into UTC weekly // interval(s). // // A converted interval may cross the UTC week boundary, // in which case it becomes two intervals. // -------------------------------------------------------- for (int i = 1; i < inputCsv.size(); i++) { String[] values = inputCsv.get(i).split(","); int localStart = Integer.parseInt(values[0].trim()); int localEnd = Integer.parseInt(values[1].trim()); String type = values[2].trim(); int offset = Integer.parseInt(values[3].trim()); List utcIntervals = convertLocalWindowToUtc( localStart, localEnd, offset ); if ("allowed".equals(type)) { allowed.addAll(utcIntervals); } else { freezes.addAll(utcIntervals); } } // Union both sets independently. allowed = mergeIntervals(allowed); freezes = mergeIntervals(freezes); // Freeze always wins. List deployable = subtractIntervals(allowed, freezes); // -------------------------------------------------------- // Apply scheduling restrictions. // -------------------------------------------------------- int earliestStart = utcNow + leadTime; List candidates = new ArrayList<>(); for (int[] window : deployable) { // We cannot start before utc_now + lead_time. int start = Math.max( window[0], earliestStart ); int end = window[1]; if (start >= end) { continue; } // There must be enough continuous deployment time. if (end - start < minContinuous) { continue; } candidates.add(new int[]{start, end}); } /* * The screenshot version of the problem explicitly says: * * t + min_continuous_minutes <= 10080 * * Since all normalized windows are already within * [0, 10080), the above clipping handles this naturally. */ candidates = mergeIntervals(candidates); List> answer = new ArrayList<>(); for (int[] interval : candidates) { if (answer.size() == k) { break; } answer.add(Arrays.asList( interval[0], interval[1] )); } return answer; } // ------------------------------------------------------------ // LOCAL CYCLIC WINDOW -> UTC WEEKLY WINDOW(S) // ------------------------------------------------------------ private static List convertLocalWindowToUtc( int localStart, int localEnd, int offset) { List result = new ArrayList<>(); // start == end means the entire local week. if (localStart == localEnd) { result.add(new int[]{0, WEEK}); return result; } // How long is this local cyclic interval? // // Normal: // [60, 180) -> 120 // // Cyclic: // [10000, 100) -> // (10080 - 10000) + 100 int duration; if (localStart < localEnd) { duration = localEnd - localStart; } else { duration = (WEEK - localStart) + localEnd; } // local = UTC + offset // // therefore // // UTC = local - offset int utcStart = normalize(localStart - offset); /* * Instead of converting every minute, * keep the interval intact. * * Example: * * local [60,180), offset +120 * * UTC start: * 60 - 120 = -60 * * normalized: * 10020 * * duration = 120 * * Conceptually: * * [10020, 10140) * * which crosses 10080. */ int utcEnd = utcStart + duration; if (utcEnd <= WEEK) { // No week-boundary crossing. result.add(new int[]{ utcStart, utcEnd }); } else { // First portion until end of week. result.add(new int[]{ utcStart, WEEK }); // Remaining portion at beginning of week. result.add(new int[]{ 0, utcEnd - WEEK }); } return result; } private static int normalize(int minute) { int normalized = minute % WEEK; if (normalized < 0) { normalized += WEEK; } return normalized; } // ------------------------------------------------------------ // MERGE / UNION // ------------------------------------------------------------ private static List mergeIntervals( List intervals) { if (intervals.isEmpty()) { return new ArrayList<>(); } intervals.sort( Comparator.comparingInt(a -> a[0]) ); List merged = new ArrayList<>(); int currentStart = intervals.get(0)[0]; int currentEnd = intervals.get(0)[1]; for (int i = 1; i < intervals.size(); i++) { int nextStart = intervals.get(i)[0]; int nextEnd = intervals.get(i)[1]; // Overlap OR touch. // // [10,20) + [20,30) // is continuously deployable [10,30). if (nextStart <= currentEnd) { currentEnd = Math.max(currentEnd, nextEnd); } else { merged.add(new int[]{ currentStart, currentEnd }); currentStart = nextStart; currentEnd = nextEnd; } } merged.add(new int[]{ currentStart, currentEnd }); return merged; } // ------------------------------------------------------------ // ALLOWED - FREEZE // ------------------------------------------------------------ private static List subtractIntervals( List allowed, List freezes) { List result = new ArrayList<>(); int freezeIndex = 0; for (int[] allowedWindow : allowed) { int allowedStart = allowedWindow[0]; int allowedEnd = allowedWindow[1]; int currentStart = allowedStart; // Skip freezes completely before this allowed window. while (freezeIndex < freezes.size() && freezes.get(freezeIndex)[1] <= allowedStart) { freezeIndex++; } int i = freezeIndex; while (i < freezes.size() && freezes.get(i)[0] < allowedEnd) { int freezeStart = freezes.get(i)[0]; int freezeEnd = freezes.get(i)[1]; // Valid portion before this freeze. if (freezeStart > currentStart) { result.add(new int[]{ currentStart, Math.min(freezeStart, allowedEnd) }); } // Move past the frozen region. currentStart = Math.max(currentStart, freezeEnd); if (currentStart >= allowedEnd) { break; } i++; } // Remaining allowed portion after freezes. if (currentStart < allowedEnd) { result.add(new int[]{ currentStart, allowedEnd }); } } return result; } private static List> convertToAnswer( List intervals) { List> answer = new ArrayList<>(); for (int[] interval : intervals) { answer.add(Arrays.asList( interval[0], interval[1] )); } return answer; } }

Quick Overview

Schedule Weekly Deployment Windows