Katkat
Back

Find the Maximum Number of Active Loans

TekionSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests the ability to solve interval overlap challenges using the sweep-line algorithm, specifically handling boundary conditions where a loan ends at the exact time another begins.

Problem Statement

You are given a list of active loans, where each loan is represented by a pair [start_time, end_time]. A loan is considered active during the interval [start, end), meaning it includes the start_time but excludes the end_time. Given this list, find the maximum number of loans that were active at any single point in time.

Function Signature

def max_active_loans(loans: List[List[int]]) -> int:

Input

  • loans: A list of lists, where each inner list contains exactly two integers [start, end] such that 0 <= start < end <= 10^9.

Output

  • An integer representing the peak number of concurrent loans.

Examples

Example 1: Input: [[1, 5], [2, 6], [5, 8]] Output: 2 Explanation: At time t=2, loans [1, 5] and [2, 6] are active (count = 2). At time t=5, the first loan ends and the third begins, so only one is active.

Example 2: Input: [[1, 10], [2, 3], [4, 5]] Output: 2

Constraints

  • 1 <= len(loans) <= 10^5
  • 0 <= start < end <= 10^9

Edge Cases

  • A single loan.
  • Multiple loans starting or ending at the same time.
  • Loans that start exactly when others end.

Hints

Hint 1

Treat the start and end times as individual events: a start event increments the count, and an end event decrements it.

Hint 2

Sort the events by time; if two events occur at the same time, process the 'end' event before the 'start' event to correctly handle the half-open interval constraint.

Hint 3

Iterate through the sorted events, maintaining a running total of active loans and tracking the maximum value reached.

Follow-up questions

  • How would your approach change if the interval was inclusive `[start, end]` (i.e., the loan is active at both the start and end time)?
  • What is the time and space complexity of your solution, and can you optimize the space if the time range is extremely large?
  • If you needed to return the specific time interval during which the maximum number of loans were active, how would you modify your algorithm?