Solve meeting scheduling and robot cleaning tasks

You are given two independent coding problems. --- ### Problem 1: Prioritized Meeting Scheduling You are asked to schedule meetings in a single meeting room. You are given an array of meeting requests. Each request is represented as a tuple: - `start`: integer start time (inclusive) - `end`: integer end time (exclusive), with `end > start` - `priority`: an integer representing the importance / value of that meeting No two meetings can overlap in time in the single room. Your goal is to choose a subset of **non-overlapping** meetings to **maximize the sum of priorities**. Write a function with the following signature (language-agnostic): ```text int maxTotalPriority(Meeting[] meetings) ``` that returns the maximum possible total priority. **Example** Input: ```text meetings = [ (1, 3, 4), (2, 4, 3), (3, 5, 2), (0, 6, 7) ] ``` One feasible schedule is to pick meetings `(1,3,4)` and `(3,5,2)` for a total priority of `4 + 2 = 6`. Another choice, `(0,6,7)`, has total priority `7`, which is better, so the answer is `7`. **Constraints** - `1 <= n <= 2 * 10^5` where `n` is the number of meetings - `0 <= start < end <= 10^9` - `-10^4 <= priority <= 10^4` (priorities can be non‑positive; you may choose to skip such meetings) - Time complexity should be **O(n log n)** or better. - You may assume `meetings` is given as a list/array in arbitrary order. Describe the algorithm and then implement the function. --- ### Problem 2: Robot Room Cleaning on an Unknown Grid You are controlling a vacuum cleaning robot in a 2D grid room. The room is divided into 1x1 cells. Each cell is either **empty** or **blocked**. The robot: - Starts on an **empty** cell in an **unknown** position in this room. - Does **not** know the layout of the room in advance. - Only knows about the cell it is currently in and whether the cell in front of it is blocked when it tries to move. You are given the following interface: ```text interface Robot { // returns true if the cell in front is open and the robot moves into the cell. // returns false if the cell in front is blocked and the robot stays in the current cell. boolean move(); // robot will stay in the same cell, but turn 90 degrees to the left. void turnLeft(); // robot will stay in the same cell, but turn 90 degrees to the right. void turnRight(); // clean the current cell. void clean(); } ``` The robot is initially facing **up** (towards negative y direction in some internal coordinate system you choose). You must implement a function: ```text void cleanRoom(Robot robot) ``` that makes the robot **clean all reachable empty cells**. You **cannot**: - Directly access the room grid or its dimensions. - Track the robot's absolute position from the environment; you must build your own coordinate system relative to the starting cell. You **can**: - Maintain an internal set of visited coordinates in your own coordinate system (e.g., treat the starting cell as `(0,0)`). - Move, turn, and clean using only the provided API. **Constraints and assumptions** - The number of reachable empty cells is at most 200. - The room is bounded (finite) but shape and size are unknown. - The robot must eventually stop after all reachable cells have been cleaned (no infinite loops). Design an algorithm and implement `cleanRoom(Robot robot)` to guarantee that all reachable empty cells are cleaned. ### Problem 2: Larger Room Variant Use the same four-method `Robot` interface and implement `Solution.cleanRoom(robot)` (or `void cleanRoom(Robot& robot)` in C++). The robot starts facing up on an unknown empty cell. A successful `move()` advances exactly one cell without turning; a failed move leaves its position and direction unchanged. Each turn changes only its direction by 90 degrees. `clean()` cleans only the current cell and does not move or turn the robot. For this variant, the hidden room is a rectangular binary grid with the following bounds. These replace the earlier 200-reachable-cell limit **only for this variant**: - `m == room.length`, `n == room[i].length`, `1 <= m <= 100`, and `1 <= n <= 200`. - Every entry is `0` (wall) or `1` (empty). - The hidden start satisfies `0 <= row < m`, `0 <= col < n`, and `room[row][col] == 1`. - All empty cells are reachable from the starting position. There can be as many as 20,000 empty cells. - Walls surround all four outside edges. The room and obstacles remain fixed while cleaning. The room, dimensions, and starting coordinates belong to the environment; none is an argument or accessible field for your implementation. Use only `move()`, `turnLeft()`, `turnRight()`, and `clean()` to interact with it. Do not implement or inspect the robot. The task succeeds when every empty cell has been cleaned and your function terminates. It returns no result; there is no required cleaning order or final position or orientation. No numerical API-call budget is specified. **Example 1** The following is an illustration of the hidden environment, not input available to `cleanRoom`. `#` is a wall, `.` is an empty cell, and `R` is the initial robot cell. The robot initially faces up. Row and column indices start at zero. ```text .....#.. ...R.#.. .#...... ###.#### ........ ``` This is a 5-by-8 room with the robot at row 1, column 3. Clean all 30 empty cells, including its starting cell. The single opening in the fourth row connects the bottom row to the rest of the room. **Example 2** For a hidden room `[[1]]` starting at `(0, 0)`, clean that cell and terminate. The successful result is the cleaning effect, not an integer count returned by `cleanRoom`. ### Practice Console Variant The existing practice material also describes a simulator-based Part 2 interface, `solution(grid, start)`, which returns the number of cleaned reachable cells. It uses a rectangular grid with each dimension at most 50 and at most 200 reachable empty cells. That variant can contain unreachable empty cells. Its simulator setup receives the grid; its exploration routine still uses only the robot API. The larger written variant above receives only a robot, has a different size bound and connectivity guarantee, and returns no count. Part 1's console uses `solution(meetings)` and additionally accepts an empty meeting list, whose answer is zero. ### Clarifying Questions - May two selected meetings meet at an endpoint, and may the selected set be empty? Yes to both. - Are the two robot size limits cumulative? No. State which variant you are solving; the larger variant permits 20,000 empty cells. - Are room dimensions or starting coordinates supplied to the cleaning function? No; they only describe the hidden environment in the robot-interface task. ### What a Strong Answer Covers - Establishes the best attainable total meeting priority, including non-positive priorities and meetings sharing an endpoint. - Meets the meeting problem's time bound and explains the space used. - Keeps robot position and orientation consistent through successful moves, blocked moves, and turns. - Cleans every required cell, terminates on cyclic layouts, and handles the largest stated room without relying on a small call-stack limit. - Distinguishes the robot-interface result from the simulator variant's returned count. ### Follow-up Questions - How would you return the selected meetings as well as their total priority? - If obstacles could move during cleaning, which guarantees in your argument would need to change?