Skip to main content
Talentd

Employee Task Duration and Concurrent Tasks - Solution & Explanation

HardPremiumFree on FleetCodeDatabase5 min read
Practice this problem

Problem Statement

Table: Tasks

+---------------+----------+
| Column Name   | Type     |
+---------------+----------+
| task_id       | int      |
| employee_id   | int      |
| start_time    | datetime |
| end_time      | datetime |
+---------------+----------+
(task_id, employee_id) is the primary key for this table.
Each row in this table contains the task identifier, the employee identifier, and the start and end times of each task.

Write a solution to find the total duration of tasks for each employee and the maximum number of concurrent tasks an employee handled at any point in time. The total duration should be rounded down to the nearest number of full hours.

Return the result table ordered by employee_id ascending order.

The result format is in the following example.

 

Example:

Input:

Tasks table:

+---------+-------------+---------------------+---------------------+
| task_id | employee_id | start_time          | end_time            |
+---------+-------------+---------------------+---------------------+
| 1       | 1001        | 2023-05-01 08:00:00 | 2023-05-01 09:00:00 |
| 2       | 1001        | 2023-05-01 08:30:00 | 2023-05-01 10:30:00 |
| 3       | 1001        | 2023-05-01 11:00:00 | 2023-05-01 12:00:00 |
| 7       | 1001        | 2023-05-01 13:00:00 | 2023-05-01 15:30:00 |
| 4       | 1002        | 2023-05-01 09:00:00 | 2023-05-01 10:00:00 |
| 5       | 1002        | 2023-05-01 09:30:00 | 2023-05-01 11:30:00 |
| 6       | 1003        | 2023-05-01 14:00:00 | 2023-05-01 16:00:00 |
+---------+-------------+---------------------+---------------------+

Output:

+-------------+------------------+----------------------+
| employee_id | total_task_hours | max_concurrent_tasks |
+-------------+------------------+----------------------+
| 1001        | 6                | 2                    |
| 1002        | 2                | 2                    |
| 1003        | 2                | 1                    |
+-------------+------------------+----------------------+

Explanation:

  • For employee ID 1001:
    • Task 1 and Task 2 overlap from 08:30 to 09:00 (30 minutes).
    • Task 7 has a duration of 150 minutes (2 hours and 30 minutes).
    • Total task time: 60 (Task 1) + 120 (Task 2) + 60 (Task 3) + 150 (Task 7) - 30 (overlap) = 360 minutes = 6 hours.
    • Maximum concurrent tasks: 2 (during the overlap period).
  • For employee ID 1002:
    • Task 4 and Task 5 overlap from 09:30 to 10:00 (30 minutes).
    • Total task time: 60 (Task 4) + 120 (Task 5) - 30 (overlap) = 150 minutes = 2 hours and 30 minutes.
    • Total task hours (rounded down): 2 hours.
    • Maximum concurrent tasks: 2 (during the overlap period).
  • For employee ID 1003:
    • No overlapping tasks.
    • Total task time: 120 minutes = 2 hours.
    • Maximum concurrent tasks: 1.

Note: Output table is ordered by employee_id in ascending order.

Approach Overview

Problem Overview: You are given task intervals for employees and need to compute task durations while also identifying tasks that run concurrently. The core challenge is detecting overlaps between time intervals and aggregating the correct duration per employee.

Approach 1: Self Join for Interval Overlap Detection (O(n²) time, O(1) extra space)

A straightforward method compares every task with every other task using a SELF JOIN. Two tasks overlap if start1 < end2 and start2 < end1. The query joins the task table to itself on employee ID and checks the overlap condition. This approach is easy to reason about because each pair of intervals is evaluated directly. The downside is scalability: with many tasks per employee the join grows quadratically, which makes it inefficient for large datasets. Still, it’s a useful baseline when first reasoning about interval overlap logic in database problems.

Approach 2: Merge Intervals with Join Logic (O(n log n) time, O(n) space)

A more efficient strategy treats task boundaries as events and merges overlapping intervals before computing durations. Start by ordering tasks by start_time. Adjacent intervals are merged when the next start occurs before the current end. In SQL, this pattern is implemented using ordered queries and joins that group overlapping ranges together. After merging, computing duration becomes a simple difference between the merged start and end timestamps.

This approach avoids repeated pairwise comparisons and processes intervals in sorted order, which reduces the complexity to the cost of sorting plus linear merging. It maps well to MySQL using joins or derived tables and works reliably even when many tasks overlap heavily. Understanding interval merging is a common technique across scheduling and log analysis problems.

SQL implementations typically rely on constructs like JOIN, ordered subqueries, and grouping logic discussed in SQL Joins. Some solutions also use analytic helpers similar to patterns found in window functions to track interval boundaries.

Recommended for interviews: The merge-based interval strategy is the expected solution. Interviewers want to see that you recognize the interval overlap pattern and reduce pairwise comparisons by sorting and merging. Starting with the self-join explanation shows you understand the overlap condition, but moving to the merge approach demonstrates stronger algorithmic and SQL optimization skills.

Solution

First, we merge the start_time and end_time for each employee_id into a new table T. Then, using the LEAD function, we calculate the start time of the next task for each employee. Next, we join table T with the Tasks table to compute the concurrent task count for each employee. Finally, we group by employee_id to calculate the total task duration and the maximum concurrent tasks for each employee.

Similar Problem:

Code

MySQL

MySQL

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Self Join Overlap DetectionO(n²)O(1)Small datasets or when demonstrating the basic interval overlap condition in SQL
Merge Intervals with Join LogicO(n log n)O(n)Large datasets where sorting and merging intervals avoids quadratic joins

Video Solution

Leetcode Interviews • ThePrimeTime • 1,196,262 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Employee Task Duration and Concurrent Tasks easy or hard?
Employee Task Duration and Concurrent Tasks is classified as a Hard problem because it combines SQL joins, interval overlap detection, and aggregation logic. Recognizing the interval merging pattern is the key difficulty.
Employee Task Duration and Concurrent Tasks Python/Java solution
Most implementations for this problem are written in SQL because it is categorized as a database query challenge. Algorithmically, Python or Java solutions would sort intervals and merge overlaps using arrays or lists to track active ranges.
How to solve Employee Task Duration and Concurrent Tasks in O(n)?
Pure O(n) is only possible if the tasks are already sorted by start time. In that case, iterate once through the intervals, track the current merged end time, and extend or close intervals when overlaps occur. Most SQL solutions require O(n log n) due to the sorting step.
What is the best approach for Employee Task Duration and Concurrent Tasks?
The most efficient approach merges overlapping task intervals after sorting by start time. Instead of comparing every pair of tasks, you process intervals in order and merge when overlaps occur. This reduces the complexity to O(n log n) due to sorting and is significantly faster than quadratic self-join solutions.
Is Employee Task Duration and Concurrent Tasks asked at Google/Amazon/Meta?
Interval overlap and scheduling queries frequently appear in database and systems design interviews at large tech companies. Variations of this problem test SQL joins, time interval logic, and event-based merging strategies used in real production analytics queries.
What data structure is used in Employee Task Duration and Concurrent Tasks?
The core structure is a list of time intervals representing tasks. SQL solutions rely on relational tables combined with joins and ordered queries to simulate interval merging or overlap detection.
What is the time complexity of Employee Task Duration and Concurrent Tasks?
A naive SQL self-join that checks every pair of tasks runs in O(n²) time. The optimized solution sorts intervals and merges overlaps, giving O(n log n) time complexity with O(n) additional space for intermediate results.

Ready to solve this problem?

Practice Employee Task Duration and Concurrent Tasks with our built-in code editor and test cases.

Practice on FleetCode
Previous

Combine Two Tables

Next

Second Highest Salary