Question

1767. Find the Subtasks That Did Not Execute

中文文档

Description

Table: Tasks

+----------------+---------+
| Column Name  | Type  |
+----------------+---------+
| task_id    | int   |
| subtasks_count | int   |
+----------------+---------+
task_id is the column with unique values for this table.
Each row in this table indicates that task_id was divided into subtasks_count subtasks labeled from 1 to subtasks_count.
It is guaranteed that 2 <= subtasks_count <= 20.

 

Table: Executed

+---------------+---------+
| Column Name   | Type  |
+---------------+---------+
| task_id     | int   |
| subtask_id  | int   |
+---------------+---------+
(task_id, subtask_id) is the combination of columns with unique values for this table.
Each row in this table indicates that for the task task_id, the subtask with ID subtask_id was executed successfully.
It is guaranteed that subtask_id <= subtasks_count for each task_id.

 

Write a solution to report the IDs of the missing subtasks for each task_id.

Return the result table in any order.

The result format is in the following example.

 

Example 1:

Input: 
Tasks table:
+---------+----------------+
| task_id | subtasks_count |
+---------+----------------+
| 1     | 3        |
| 2     | 2        |
| 3     | 4        |
+---------+----------------+
Executed table:
+---------+------------+
| task_id | subtask_id |
+---------+------------+
| 1     | 2      |
| 3     | 1      |
| 3     | 2      |
| 3     | 3      |
| 3     | 4      |
+---------+------------+
Output: 
+---------+------------+
| task_id | subtask_id |
+---------+------------+
| 1     | 1      |
| 1     | 3      |
| 2     | 1      |
| 2     | 2      |
+---------+------------+
Explanation: 
Task 1 was divided into 3 subtasks (1, 2, 3). Only subtask 2 was executed successfully, so we include (1, 1) and (1, 3) in the answer.
Task 2 was divided into 2 subtasks (1, 2). No subtask was executed successfully, so we include (2, 1) and (2, 2) in the answer.
Task 3 was divided into 4 subtasks (1, 2, 3, 4). All of the subtasks were executed successfully.

Solutions

Solution 1: Recursive Table Generation + Left Join

We can generate a table recursively that contains all pairs of (parent task, child task), and then use a left join to find the pairs that have not been executed.

# Write your MySQL query statement below
WITH RECURSIVE
  T(task_id, subtask_id) AS (
    SELECT
      task_id,
      subtasks_count
    FROM Tasks
    UNION ALL
    SELECT
      task_id,
      subtask_id - 1
    FROM t
    WHERE subtask_id > 1
  )
SELECT
  T.*
FROM
  T
  LEFT JOIN Executed USING (task_id, subtask_id)
WHERE Executed.subtask_id IS NULL;