Problem

Given a list of closed intervals [[start, end], ...], find a point (an integer coordinate) at which the maximum number of intervals overlap. Return one such point; if multiple points achieve the same maximum, any one is acceptable.

Example

1
2
3
4

Input: intervals = [[1,4], [2,5], [9,12], [5,9], [5,12]]
Output: 5

Explanation: At time `5` three intervals overlap: [2,5], [5,9], and [5,12].

Solution

Two common approaches: (A) sweep-line over start/end events, and (B) a min-heap of end times while scanning starts. The sweep-line is simpler and directly gives the point of maximum overlap.

Method 1 - Sweep-line (event counting)

Intuition

Create start and end events for each interval. If we process start events as +1 and end events as -1 (processing starts before ends at the same coordinate), a running sum tracks how many intervals currently cover a point. The maximum running sum and its event coordinate give the desired point.

Approach

  1. Build a list of events (x, delta) where delta = +1 for start and delta = -1 for end.
  2. Sort events by x; if two events have the same x, process start (+1) before end (-1).
  3. Iterate events accumulating count += delta. Track the maximum count and the corresponding x where it first occurs.
  4. Return the x with the maximum overlap.

Edge cases:

  • Intervals with identical start and end should be treated as covering that point.
  • If multiple adjacent integer points have the same max count, this returns the first event coordinate where the max occurs.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
 public:
	int maxOverlapPoint(const vector<pair<int,int>>& intervals) {
		vector<pair<int,int>> events;
		for (auto &p : intervals) {
			events.push_back({p.first, 1});
			events.push_back({p.second, -1});
		}
		sort(events.begin(), events.end(), [](const auto &a, const auto &b) {
			if (a.first != b.first) return a.first < b.first;
			return a.second > b.second; // start(+1) before end(-1)
		});
		int cnt = 0, best = 0, bestX = 0;
		for (auto &e : events) {
			cnt += e.second;
			if (cnt > best) { best = cnt; bestX = e.first; }
		}
		return bestX;
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

package main

import "sort"

func maxOverlapPoint(intervals [][2]int) int {
	events := make([][2]int, 0, len(intervals)*2)
	for _, seg := range intervals {
		events = append(events, [2]int{seg[0], 1})
		events = append(events, [2]int{seg[1], -1})
	}
	sort.Slice(events, func(i, j int) bool {
		if events[i][0] != events[j][0] { return events[i][0] < events[j][0] }
		return events[i][1] > events[j][1]
	})
	cnt, best, bestX := 0, 0, 0
	for _, e := range events {
		cnt += e[1]
		if cnt > best { best = cnt; bestX = e[0] }
	}
	return bestX
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
		public int maxOverlapPoint(int[][] intervals) {
				List<int[]> events = new ArrayList<>();
				for (int[] seg : intervals) {
						events.add(new int[]{seg[0], 1});
						events.add(new int[]{seg[1], -1});
				}
				Collections.sort(events, (a, b) -> {
						if (a[0] != b[0]) return Integer.compare(a[0], b[0]);
						return Integer.compare(b[1], a[1]); // start (+1) before end (-1)
				});
				int cnt = 0, best = 0, bestX = 0;
				for (int[] e : events) {
						cnt += e[1];
						if (cnt > best) { best = cnt; bestX = e[0]; }
				}
				return bestX;
		}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
		def max_overlap_point(self, intervals: list[tuple[int,int]]) -> int:
				events: list[tuple[int,int]] = []
				for s, e in intervals:
						events.append((s, 1))
						events.append((e, -1))
				events.sort(key=lambda x: (x[0], -x[1]))  # start before end at same x
				cnt = best = 0
				best_x = 0
				for x, delta in events:
						cnt += delta
						if cnt > best:
								best = cnt
								best_x = x
				return best_x

Complexity

  • ⏰ Time complexity: O(n log n) for sorting the 2n events; the scan is O(n), so total O(n log n).
  • 🧺 Space complexity: O(n) to store 2n events and output-related data.

Method 2 - Min-heap of end times (scan starts)

Intuition

Maintain a min-heap of interval end times while iterating intervals sorted by start. The heap contains the end times of intervals that cover the current start. The heap size is the number of overlapping intervals at that start — track the max and record the start where it occurs.

Approach

  1. Sort intervals by start.
  2. Use a min-heap for end times. For each interval, pop all ends less than the current start (they no longer overlap), push current end, and check heap size for maximum.
  3. Return the start where heap size reached its maximum.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class SolutionHeap {
 public:
	int maxOverlapPoint(vector<pair<int,int>> intervals) {
		sort(intervals.begin(), intervals.end());
		priority_queue<int, vector<int>, greater<int>> pq;
		int best = 0, bestX = 0;
		for (auto &seg : intervals) {
			int s = seg.first, e = seg.second;
			while (!pq.empty() && pq.top() < s) pq.pop();
			pq.push(e);
			if ((int)pq.size() > best) { best = pq.size(); bestX = s; }
		}
		return bestX;
	}
};
1

// Similar approach using a min-heap of ints (end times) can be implemented in Go.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

import java.util.Arrays;
import java.util.PriorityQueue;

class SolutionHeap {
		public int maxOverlapPoint(int[][] intervals) {
				Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
				PriorityQueue<Integer> pq = new PriorityQueue<>();
				int best = 0, bestX = 0;
				for (int[] seg : intervals) {
						int s = seg[0], e = seg[1];
						while (!pq.isEmpty() && pq.peek() < s) pq.poll();
						pq.offer(e);
						if (pq.size() > best) { best = pq.size(); bestX = s; }
				}
				return bestX;
		}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

import heapq

class SolutionHeap:
		def max_overlap_point(self, intervals: list[tuple[int,int]]) -> int:
				if not intervals: return 0
				intervals.sort(key=lambda x: x[0])
				heap: list[int] = []
				best = 0
				best_x = 0
				for s, e in intervals:
						while heap and heap[0] < s:
								heapq.heappop(heap)
						heapq.heappush(heap, e)
						if len(heap) > best:
								best = len(heap)
								best_x = s
				return best_x

Complexity

  • ⏰ Time complexity: O(n log n) for sorting plus heap operations — overall O(n log n).
  • 🧺 Space complexity: O(n) for the heap and auxiliary storage.

References