CDN Image Upload Render Scheduler

Problem Narrative

You’re building the image pipeline for a high-traffic e-commerce marketplace (10M+ DAUs). Product pages show a grid of images; each image must be uploaded, then may be served from cache (if already present), and finally rendered on the client. Poor scheduling increases tail latency and hurts conversion.

To model this, you are given a stream of image requests. Each request has an image_id, an upload_time (seconds needed if not cached), and a render_time (seconds needed on the client once the bytes are available). The system has:

1. A cache with capacity C images (LRU eviction).
2. A single upload worker (can upload only one image at a time).
3. A single render worker (can render only one image at a time).

If an image is already in cache at request time, its upload is skipped (0 seconds) and it becomes immediately eligible to render.

Task

Implement schedule_images(requests, C) that returns the minimum possible time (in seconds) to finish rendering all requested images, assuming you can choose which eligible upload/render job to run next at any time.

Input

• requests: List[Tuple[int, int, int]] where each tuple is (image_id, upload_time, render_time) in the order requests arrive at time t=0 (all requests are known upfront).
• C: integer cache capacity.

Output

• Return an integer: the minimum makespan to complete all renders.

Rules & Clarifications

• All requests are considered to arrive at time 0 (you’re optimizing scheduling, not arrival times).
• Uploading an image places it into the cache after upload completes.
• If cache is full when an upload completes, evict the least recently used image. “Use” means: referenced by a request (even if cached) or inserted by upload completion.
• Rendering requires the image bytes to be available (cached or just uploaded). Rendering does not change cache contents.
• You may interleave uploads and renders; both workers run in parallel.

Constraints

• 1 <= len(requests) <= 2 * 10^5
• 0 <= upload_time, render_time <= 10^6
• 1 <= C <= 10^5
• image_id fits in 32-bit signed int

Notes

This is a scheduling + caching problem: you must account for LRU cache hits/misses and overlap of the upload/render pipelines to minimize the overall completion time.