> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/interview/holiday.md).

# 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:

1. A **duration** Di (the show runs for Di minutes whenever it starts).
2. **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

1. 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, 110
```

### Sample 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 120
```

### Answer

{% code fullWidth="true" %}

```java
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
    }
}
```

{% endcode %}