LeetCode 3156 - Employee Task Duration and Concurrent Tasks

The problem gives us a table named Tasks, where each row represents a task assigned to an employee. Every task has a start timestamp and an end timestamp. Multiple tasks may overlap in time for the same employee. We need to compute two values for every employee: 1.

leetcodeharddatabase

LeetCode Problem 3156

Difficulty: 🔴 Hard
Topics: Database

Solution

Problem Understanding

The problem gives us a table named Tasks, where each row represents a task assigned to an employee. Every task has a start timestamp and an end timestamp. Multiple tasks may overlap in time for the same employee.

We need to compute two values for every employee:

  1. The total amount of time the employee spent working on tasks.
  2. The maximum number of tasks the employee was handling simultaneously at any moment.

The important detail is that overlapping time intervals must not be double counted when calculating the total duration. If two tasks overlap for 30 minutes, those 30 minutes should contribute only once to the employee's total working time.

For example, suppose an employee has:

  • Task A from 08:00 to 09:00
  • Task B from 08:30 to 10:30

The employee was working continuously from 08:00 to 10:30, which is 150 minutes total, not 180 minutes. The overlapping 30 minute window should only be counted once.

The second metric is different. For concurrent tasks, we do want to count overlaps. During the interval from 08:30 to 09:00, the employee was handling two tasks at the same time, so the concurrency is 2 during that period.

The final output should contain:

  • employee_id
  • total_task_hours
  • max_concurrent_tasks

The total duration must be rounded down to full hours. This means:

  • 150 minutes becomes 2 hours
  • 359 minutes becomes 5 hours

The result must be ordered by employee_id in ascending order.

What the Input Represents

Each row contains:

Column Meaning
task_id Unique identifier for the task
employee_id Employee assigned to the task
start_time When the task started
end_time When the task ended

The pair (task_id, employee_id) is unique.

Important Observations

The key challenge is handling overlapping intervals correctly.

For total working time:

  • We must merge overlapping intervals before calculating duration.

For maximum concurrency:

  • We must detect the maximum number of active intervals at any timestamp.

These are related interval-processing problems, but they require different computations.

Important Edge Cases

Tasks that overlap partially can easily lead to double counting if intervals are summed independently.

Tasks that touch exactly at boundaries are another subtle case. If one task ends at 10:00 and another starts at 10:00, they are not overlapping. The implementation must process end events before start events at the same timestamp.

Employees may have:

  • Only one task
  • Completely overlapping tasks
  • Nested intervals
  • Multiple disjoint working periods

The problem guarantees valid timestamps, meaning every task has a proper start and end time.

Approaches

Brute Force Approach

A naive solution would process every minute or second in the timeline for each employee.

For each employee:

  1. Find the earliest start time and latest end time.
  2. Iterate through every unit of time.
  3. Count how many tasks are active.
  4. Track:
  • Whether at least one task is active, for total duration
  • The maximum active task count, for concurrency

This approach is conceptually simple because it directly simulates the timeline. However, datetime ranges can be very large, making this extremely inefficient.

Another brute force approach would compare every interval against every other interval to detect overlaps and merge manually. This still becomes expensive as the number of tasks grows.

Key Insight

The important observation is that interval problems can be solved efficiently using a sweep line algorithm.

Instead of examining every moment in time, we only care about moments where something changes:

  • A task starts
  • A task ends

For each employee:

  • Convert every interval into two events:

  • (start_time, +1)

  • (end_time, -1)

  • Sort events chronologically

  • Sweep through them while maintaining the current number of active tasks

This immediately gives us maximum concurrency.

For total duration:

  • Sort intervals by start time
  • Merge overlapping intervals
  • Sum the merged durations

Both operations are efficient because sorting dominates the runtime.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(N × T) O(1) Simulates every time unit, impractical for large ranges
Optimal O(N log N) O(N) Uses interval sorting and sweep line processing

Here:

  • N is the number of tasks
  • T is the size of the time range being simulated

Algorithm Walkthrough

Step 1: Group Tasks by Employee

We first organize all tasks by employee_id.

This allows us to process each employee independently because intervals from different employees never interact.

We store:

  • The list of intervals for merging
  • The list of start/end events for concurrency

Step 2: Sort Intervals by Start Time

For each employee, sort intervals using:

(start_time, end_time)

Sorting allows overlapping intervals to appear next to each other, which makes merging straightforward.

Step 3: Merge Overlapping Intervals

We maintain:

  • current_start
  • current_end

For every interval:

  • If the next interval starts before or at current_end, merge them:

  • Extend current_end

  • Otherwise:

  • Finalize the previous merged interval

  • Start a new one

Every finalized merged interval contributes:

merged_end - merged_start

to the total working duration.

Step 4: Convert Tasks Into Sweep Events

For concurrency tracking:

  • Add (start_time, +1)
  • Add (end_time, -1)

The +1 means a task becomes active.

The -1 means a task stops being active.

Step 5: Sort Events Carefully

Events must be sorted by:

  1. Timestamp
  2. Event type

End events must come before start events at the same timestamp.

Why?

Suppose:

  • Task A ends at 10:00
  • Task B starts at 10:00

These tasks do not overlap.

If we processed starts first:

  • Active count would temporarily become 2
  • This would incorrectly increase concurrency

So we process:

(end, -1) before (start, +1)

at identical timestamps.

Step 6: Sweep Through Events

Maintain:

  • active_tasks
  • max_concurrent

For every event:

  • Update active_tasks
  • Update maximum

This produces the highest concurrency encountered during the sweep.

Step 7: Convert Minutes to Full Hours

After computing total duration:

floor(total_minutes / 60)

This satisfies the requirement to round down to full hours.

Why it works

The correctness comes from two interval-processing invariants.

For total duration, sorting intervals guarantees that every overlapping interval appears adjacent to the interval it overlaps with. Therefore, merging sequentially produces the exact union of all working intervals without double counting.

For concurrency, the sweep line invariant is that active_tasks always equals the number of intervals currently covering the sweep timestamp. Since every interval contributes exactly one start and one end event, the maximum value reached during the sweep is precisely the maximum concurrent task count.

Python Solution

from collections import defaultdict
from typing import List

class Solution:
    def employeeTaskDurationAndConcurrentTasks(self, tasks: List[List]) -> List[List[int]]:
        employee_intervals = defaultdict(list)

        for task_id, employee_id, start_time, end_time in tasks:
            employee_intervals[employee_id].append((start_time, end_time))

        result = []

        for employee_id in sorted(employee_intervals.keys()):
            intervals = employee_intervals[employee_id]

            # Sort intervals for merging
            intervals.sort()

            # Merge intervals to calculate total working duration
            merged_minutes = 0

            current_start, current_end = intervals[0]

            for start, end in intervals[1:]:
                if start <= current_end:
                    current_end = max(current_end, end)
                else:
                    merged_minutes += int(
                        (current_end - current_start).total_seconds() // 60
                    )
                    current_start, current_end = start, end

            merged_minutes += int(
                (current_end - current_start).total_seconds() // 60
            )

            total_task_hours = merged_minutes // 60

            # Sweep line for maximum concurrency
            events = []

            for start, end in intervals:
                events.append((start, 1))
                events.append((end, -1))

            # End events before start events at same timestamp
            events.sort(key=lambda x: (x[0], x[1]))

            active_tasks = 0
            max_concurrent_tasks = 0

            for _, delta in events:
                active_tasks += delta
                max_concurrent_tasks = max(max_concurrent_tasks, active_tasks)

            result.append([
                employee_id,
                total_task_hours,
                max_concurrent_tasks
            ])

        return result

The implementation starts by grouping intervals by employee using a defaultdict. This ensures each employee's tasks can be processed independently.

The interval merging section computes the union of all working periods. By sorting intervals first, overlapping segments become adjacent, allowing a single linear scan to merge them correctly.

The duration is measured in minutes using:

(current_end - current_start).total_seconds() // 60

After summing merged durations, integer division converts minutes into full hours.

The concurrency computation uses a classic sweep line strategy. Every interval generates a start event and an end event. Sorting events ensures chronological processing, while the secondary sort key guarantees end events are processed before start events at identical timestamps.

The running active_tasks counter always represents the number of currently active tasks, and the maximum observed value becomes the answer.

Go Solution

package main

import (
	"sort"
	"time"
)

type Task struct {
	TaskID     int
	EmployeeID int
	StartTime  time.Time
	EndTime    time.Time
}

type Result struct {
	EmployeeID          int
	TotalTaskHours      int
	MaxConcurrentTasks  int
}

type Event struct {
	Time  time.Time
	Delta int
}

func employeeTaskDurationAndConcurrentTasks(tasks []Task) []Result {
	employeeIntervals := make(map[int][]Task)

	for _, task := range tasks {
		employeeIntervals[task.EmployeeID] = append(
			employeeIntervals[task.EmployeeID],
			task,
		)
	}

	employeeIDs := make([]int, 0, len(employeeIntervals))

	for id := range employeeIntervals {
		employeeIDs = append(employeeIDs, id)
	}

	sort.Ints(employeeIDs)

	results := []Result{}

	for _, employeeID := range employeeIDs {
		intervals := employeeIntervals[employeeID]

		sort.Slice(intervals, func(i, j int) bool {
			return intervals[i].StartTime.Before(intervals[j].StartTime)
		})

		// Merge intervals
		currentStart := intervals[0].StartTime
		currentEnd := intervals[0].EndTime

		totalMinutes := 0

		for i := 1; i < len(intervals); i++ {
			start := intervals[i].StartTime
			end := intervals[i].EndTime

			if !start.After(currentEnd) {
				if end.After(currentEnd) {
					currentEnd = end
				}
			} else {
				totalMinutes += int(currentEnd.Sub(currentStart).Minutes())
				currentStart = start
				currentEnd = end
			}
		}

		totalMinutes += int(currentEnd.Sub(currentStart).Minutes())

		totalTaskHours := totalMinutes / 60

		// Sweep line for concurrency
		events := []Event{}

		for _, interval := range intervals {
			events = append(events, Event{
				Time:  interval.StartTime,
				Delta: 1,
			})

			events = append(events, Event{
				Time:  interval.EndTime,
				Delta: -1,
			})
		}

		sort.Slice(events, func(i, j int) bool {
			if events[i].Time.Equal(events[j].Time) {
				return events[i].Delta < events[j].Delta
			}
			return events[i].Time.Before(events[j].Time)
		})

		activeTasks := 0
		maxConcurrentTasks := 0

		for _, event := range events {
			activeTasks += event.Delta

			if activeTasks > maxConcurrentTasks {
				maxConcurrentTasks = activeTasks
			}
		}

		results = append(results, Result{
			EmployeeID:         employeeID,
			TotalTaskHours:     totalTaskHours,
			MaxConcurrentTasks: maxConcurrentTasks,
		})
	}

	return results
}

The Go implementation follows the same logic as the Python solution but uses explicit structs for tasks, events, and results.

Go does not have Python's built in tuple sorting, so sort.Slice is used with custom comparator functions.

Time calculations use:

currentEnd.Sub(currentStart).Minutes()

The concurrency sweep also requires explicit event structs with timestamp and delta fields.

Since Go slices default to empty rather than nil in most practical usage, no special handling is required for result construction.

Worked Examples

Example 1

Input:

1001:
[08:00, 09:00]
[08:30, 10:30]
[11:00, 12:00]
[13:00, 15:30]

Interval Merging

Current Interval Action Merged State
08:00-09:00 Start merge 08:00-09:00
08:30-10:30 Overlaps 08:00-10:30
11:00-12:00 No overlap finalize 08:00-10:30
13:00-15:30 No overlap finalize 11:00-12:00

Final merged intervals:

Interval Duration
08:00-10:30 150 min
11:00-12:00 60 min
13:00-15:30 150 min

Total:

150 + 60 + 150 = 360 minutes
360 // 60 = 6 hours

Sweep Events

Time Delta Active Tasks
08:00 +1 1
08:30 +1 2
09:00 -1 1
10:30 -1 0
11:00 +1 1
12:00 -1 0
13:00 +1 1
15:30 -1 0

Maximum concurrency:

2

Example 2

Input:

1002:
[09:00, 10:00]
[09:30, 11:30]

Merging

Interval Result
09:00-10:00 Start
09:30-11:30 Merge

Merged interval:

09:00-11:30

Duration:

150 minutes
150 // 60 = 2 hours

Sweep

Time Delta Active
09:00 +1 1
09:30 +1 2
10:00 -1 1
11:30 -1 0

Maximum concurrency:

2

Example 3

Input:

1003:
[14:00, 16:00]

No merging required.

Duration:

120 minutes = 2 hours

Concurrency:

1

Complexity Analysis

Measure Complexity Explanation
Time O(N log N) Sorting intervals and events dominates runtime
Space O(N) Additional storage for grouped intervals and sweep events

The algorithm processes each employee independently, but overall complexity is dominated by sorting all intervals and events. Since sorting requires O(N log N) time, that becomes the total complexity.

The auxiliary space comes from storing grouped intervals and event arrays.

Test Cases

from datetime import datetime

s = Solution()

# Example case with overlaps
tasks1 = [
    [1, 1001, datetime(2023, 5, 1, 8, 0), datetime(2023, 5, 1, 9, 0)],
    [2, 1001, datetime(2023, 5, 1, 8, 30), datetime(2023, 5, 1, 10, 30)],
    [3, 1001, datetime(2023, 5, 1, 11, 0), datetime(2023, 5, 1, 12, 0)],
    [7, 1001, datetime(2023, 5, 1, 13, 0), datetime(2023, 5, 1, 15, 30)],
]

assert s.employeeTaskDurationAndConcurrentTasks(tasks1) == [
    [1001, 6, 2]
]  # standard overlap case

# Two overlapping tasks
tasks2 = [
    [4, 1002, datetime(2023, 5, 1, 9, 0), datetime(2023, 5, 1, 10, 0)],
    [5, 1002, datetime(2023, 5, 1, 9, 30), datetime(2023, 5, 1, 11, 30)],
]

assert s.employeeTaskDurationAndConcurrentTasks(tasks2) == [
    [1002, 2, 2]
]  # partial overlap

# Single task
tasks3 = [
    [6, 1003, datetime(2023, 5, 1, 14, 0), datetime(2023, 5, 1, 16, 0)],
]

assert s.employeeTaskDurationAndConcurrentTasks(tasks3) == [
    [1003, 2, 1]
]  # one interval only

# Completely non-overlapping intervals
tasks4 = [
    [1, 1, datetime(2023, 1, 1, 8, 0), datetime(2023, 1, 1, 9, 0)],
    [2, 1, datetime(2023, 1, 1, 10, 0), datetime(2023, 1, 1, 11, 0)],
]

assert s.employeeTaskDurationAndConcurrentTasks(tasks4) == [
    [1, 2, 1]
]  # no overlap at all

# Fully nested intervals
tasks5 = [
    [1, 1, datetime(2023, 1, 1, 8, 0), datetime(2023, 1, 1, 12, 0)],
    [2, 1, datetime(2023, 1, 1, 9, 0), datetime(2023, 1, 1, 10, 0)],
    [3, 1, datetime(2023, 1, 1, 9, 30), datetime(2023, 1, 1, 9, 45)],
]

assert s.employeeTaskDurationAndConcurrentTasks(tasks5) == [
    [1, 4, 3]
]  # nested overlap increases concurrency

# Touching intervals should not overlap
tasks6 = [
    [1, 1, datetime(2023, 1, 1, 8, 0), datetime(2023, 1, 1, 9, 0)],
    [2, 1, datetime(2023, 1, 1, 9, 0), datetime(2023, 1, 1, 10, 0)],
]

assert s.employeeTaskDurationAndConcurrentTasks(tasks6) == [
    [1, 2, 1]
]  # boundary touching only

# Multiple employees
tasks7 = [
    [1, 1, datetime(2023, 1, 1, 8, 0), datetime(2023, 1, 1, 10, 0)],
    [2, 2, datetime(2023, 1, 1, 9, 0), datetime(2023, 1, 1, 11, 0)],
]

assert s.employeeTaskDurationAndConcurrentTasks(tasks7) == [
    [1, 2, 1],
    [2, 2, 1]
]  # independent employee processing

Test Summary

Test Why
Standard overlap example Verifies merging and concurrency together
Partial overlap Tests overlap duration subtraction
Single interval Simplest valid input
Non-overlapping intervals Ensures no accidental merging
Nested intervals Validates high concurrency handling
Boundary-touching intervals Ensures end-before-start ordering
Multiple employees Confirms independent grouping logic

Edge Cases

Tasks That Touch at Boundaries

One subtle edge case occurs when one task ends exactly when another begins.

Example:

[08:00, 09:00]
[09:00, 10:00]

These tasks should not be considered concurrent because there is no overlapping time interval.

A buggy implementation that processes start events before end events at the same timestamp would incorrectly report concurrency as 2.

The solution avoids this by sorting events so that end events are processed before start events at identical timestamps.

Completely Nested Tasks

Another tricky case is when one interval fully contains several others.

Example:

[08:00, 12:00]
[09:00, 10:00]
[09:30, 09:45]

The total working duration should still be only 4 hours because all smaller tasks occur inside the large interval.

However, concurrency should rise to 3 during the innermost overlap.

The interval merge logic correctly preserves only the outer interval for duration calculations, while the sweep line correctly counts all simultaneous active tasks.

Multiple Disjoint Working Periods

Employees may work in several completely separate blocks throughout the day.

Example:

[08:00, 09:00]
[11:00, 12:00]
[14:00, 16:00]

A faulty merge implementation could accidentally combine unrelated intervals.

The algorithm prevents this by only merging intervals when:

next_start <= current_end

Otherwise, the current merged interval is finalized and a new one begins.

This guarantees accurate duration totals for disjoint intervals.