Peak Concurrent Sensor Activity Problem

Peak Concurrent Sensor Activity Problem — ExecCode Medium DSA Practice

Solve the Peak Concurrent Sensor Activity problem on ExecCode. Free online medium DSA practice in Arrays - Basics. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Description A monitoring system tracks n wireless sensors. Sensor i is active on every integer timestamp t with li <= t <= ri (both ends inclusive). Sensors may share the same active window. You may choose one integer time t (anywhere on the number line). What is the largest number of sensors that can be active at that exact time? Task You are given n closed integer intervals [li, ri]. Choose a single integer x such that the number of intervals containing x is maximized. Compute that maximum count. Formally, interval [l, r] contains x iff l <= x <= r.

Examples

Input 2 1 3 5 7 ; Output 1. Input 3 1 5 2 6 3 7 ; Output 3. Input 4 1 4 2 5 7 9 3 8 ; Output 3

Constraints

1 <= n <= 2*10^5; -10^18 <= li <= ri <= 10^18; intervals are closed.

Practice Peak Concurrent Sensor Activity free on ExecCode. Browse DSA problems, topic map, and placement guides.