> 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 %}


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mayanktyagi3111.gitbook.io/interview-prep/interview/holiday.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.