Holiday
Problem Statement
Bob has a holiday from school. He decides to spend his free time—exactly M minutes—watching TV shows. There are N TV shows he likes, and each TV show i has:
A duration Di (the show runs for Di minutes whenever it starts).
Three start times ti1, ti2, ti3. A TV show begins at one of these start times and continues for Di minutes from that start time.
Bob can switch from one show to another at any moment, as long as the show he switches to is running at that moment. Bob wants to fill all M minutes with no gaps—i.e., he can start from any (x) minutes to minute x + M, he must be continuously watching some show that is running.
Determine whether it is possible for Bob to schedule his TV-watching in such a way that he spends the entire M minutes watching shows with no idle time in between.
Notes
A TV show i starts at one of its start times ti and runs for Di consecutive minutes.
Bob does not need to watch a particular TV show from its beginning or for its entire duration. He can jump into a show midway or leave it before it ends, as long as the show is still running.
Bob can instantly switch to another show (no transition time) if the other show is also running at that exact moment.
Bob doesn't watch a show more than once, i.e - he will not watch a show 2 times as different slots.
Function Description
You are to implement a function, often named solve() in competitive programming, which reads the inputs and outputs a single line for each test case:
Print "YES" if Bob can spend all M minutes continuously watching TV shows (with no gaps).
Print "NO" otherwise.
Input Format for Custom Testing
For each test case:
An integer N — the number of TV shows Bob likes.
An integer M — the total free time Bob wants to fill.
Then N lines follow, each describing a TV show’s features. For instance, each line will contain: Di, ti1, ti2, ti3 where Di is the show’s duration, and each ti is one possible start time for that show.
Output Format
For each test case, print "YES" if Bob can spend his entire MM minutes watching TV shows back-to-back, or "NO" if it is not possible.
Constraints
1 ≤ N ≤ 10
1 ≤ M ≤ 300
0 ≤ Di, ti ≤ M
Sample Input
4 -> N
120 -> M
1) 60, 10, 60, 100
2) 30, 0, 50, 90
3) 20, 0, 20, 40
4) 50, 50, 70, 110Sample Output
YES // Start with 3) at 0 time -> Jump to 1) at 10 and watch till 70 -> Jump to 4) at 70 and watch till 120Answer
import java.util.*;
public class Solution {
static class Interval {
int showIndex, start, end;
Interval(int showIndex, int start, int end) {
this.showIndex = showIndex;
this.start = start;
this.end = end;
}
}
public static int getBit(int num, int index) {
return (num >> index) & 1;
}
// Set a bit to one
public static int setBit(int num, int index) {
return num | (1 << index);
}
public static String solve(int m, List<List<Integer>> shows) {
boolean canReachM = false;
List<Interval> list = new ArrayList<>();
// Create node for all shows and sort them on start time
for (int i = 0; i < shows.size(); i++) {
List<Integer> showDetails = shows.get(i);
int showTime = showDetails.get(0);
for (int j = 1; j <= 3; j++) {
int startTime = showDetails.get(j);
Interval node = new Interval(i, startTime, startTime + showTime);
list.add(node);
}
}
list.sort((a, b) -> a.start - b.start);
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
/**
* Initialize DP array where each slot has a hashmap.
* Key of hashmap - an integer whose bits represent the selected shows
* Value of hashmap - start,end where the diff is max for selected shows
*/
Map<Integer, int[]>[] dp = new Map[list.size()];
for (int i = list.size() - 1; i >= 0; i--) {
Interval currentNode = list.get(i);
dp[i] = new HashMap<>();
dp[i].put(setBit(0, currentNode.showIndex), new int[] { currentNode.start, currentNode.end });
if (currentNode.end - currentNode.start >= m) {
canReachM = true;
break;
}
for (int j = i + 1; j < list.size(); j++) {
Interval nextNode = list.get(j);
if (currentNode.end >= nextNode.start && currentNode.showIndex != nextNode.showIndex) {
Map<Integer, int[]> possiblePaths = dp[j];
for (Integer path : possiblePaths.keySet()) {
int[] duration = possiblePaths.get(path);
if (getBit(path, currentNode.showIndex) == 0) {
int newPath = setBit(path, currentNode.showIndex);
int newStart = currentNode.start;
int newEnd = Math.max(currentNode.end, duration[1]);
if (dp[i].containsKey(newPath) && dp[i].get(newPath)[1] < newEnd) {
dp[i].put(newPath, new int[] { newStart, newEnd });
} else {
dp[i].put(newPath, new int[] { newStart, newEnd });
}
if (dp[i].get(newPath)[1] - dp[i].get(newPath)[0] >= m) {
canReachM = true;
break;
}
}
}
}
if (canReachM) {
break;
}
}
if (canReachM) {
break;
}
}
return canReachM ? "YES" : "NO";
}
public static void main(String[] args) {
// Example test case 1
List<List<Integer>> shows1 = new ArrayList<>();
shows1.add(Arrays.asList(60, 10, 60, 100));
shows1.add(Arrays.asList(30, 0, 50, 90));
shows1.add(Arrays.asList(20, 0, 20, 40));
shows1.add(Arrays.asList(50, 50, 70, 110));
System.out.println(solve(120, shows1)); // Expected output: YES
// Example test case 2
List<List<Integer>> shows2 = new ArrayList<>();
shows2.add(Arrays.asList(50, 30, 60, 100));
shows2.add(Arrays.asList(30, 40, 50, 90));
shows2.add(Arrays.asList(20, 0, 20, 40));
shows2.add(Arrays.asList(50, 50, 70, 110));
System.out.println(solve(120, shows2)); // Expected output: YES
}
}Last updated