Overview

Given \(N\) apple trees lined up on a straight line, find the maximum number of trees that can be contained within an interval of length \(K\) or less.

Analysis

There are three key points for solving this problem:

1. Sorting the coordinates: The tree coordinates \(X_i\) are given in an arbitrary order. To efficiently count the trees within an interval, the standard approach is to first sort the coordinates in ascending order. By sorting, we can leverage the property that “consecutively numbered trees are contained in the same interval.”

2. Choosing the optimal interval: Although there are infinitely many possible “intervals of length \(K\) or less,” we can observe that the left endpoint \(L\) of an optimal interval can always be set to coincide with some apple tree’s coordinate \(X_i\). This is because even if you start the interval at an intermediate position, shifting it left to align with a tree will never make things worse.

3. Limitations of the naive approach: Consider the method where, for every tree \(i\), we count “how many trees are within the range from tree \(i\) (as the left endpoint) to \(X_i + K\) (as the right endpoint).”

   • Checking all other trees for each tree takes \(O(N^2)\) time.
   • Since \(N = 2 \times 10^5\) in this problem, \(N^2 = 4 \times 10^{10}\), which will not finish within the time limit. Therefore, a more efficient two-pointer technique (or binary search) is needed.

Algorithm

Apply the two-pointer technique (Two Pointers) to the sorted coordinates.

1. Sort the tree coordinates \(X\) in ascending order.
2. Prepare a pointer left pointing to the left end of the interval and a pointer right pointing to the right end.
3. Advance right one by one from \(0\) to \(N-1\), performing the following operations:
   • While the current interval length X[right] - X[left] exceeds \(K\), advance left to the right.
   • Once the length is \(K\) or less, compute the number of trees in the interval: right - left + 1.
   • Update the maximum number of trees found so far.

In this method, both left and right traverse the array only once each, so it operates very efficiently.

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting the coordinates takes \(O(N \log N)\).
  • The two-pointer part takes \(O(N)\).
  • Overall, sorting is the dominant factor, resulting in \(O(N \log N)\).
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used for the array storing the tree coordinates.

Implementation Notes

• Don’t forget to sort: Since the input coordinates are in no particular order, you must always perform sort() first.

• Interval length check: “The interval length is \(K\) or less” in the problem statement means that, with \(R\) as the right endpoint and \(L\) as the left endpoint, \(R - L \leq K\) must hold. In the code, this condition is maintained by advancing left while x[right] - x[left] > k.

• Large input: Since \(N\) can be large, in Python it is advisable to read input efficiently using methods such as sys.stdin.read().split().

  Source Code

import sys

def main():
    # 入力を標準入力からすべて読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: りんごの木の本数, K: 区間の最大長
    n = int(input_data[0])
    k = int(input_data[1])
    
    # x: 各りんごの木の座標
    x = list(map(int, input_data[2:]))
    
    # 座標を昇順にソートする
    x.sort()
    
    max_trees = 0
    left = 0
    
    # しゃくとり法（Two Pointers）を用いて、
    # x[right] - x[left] <= k を満たす最大の個数 (right - left + 1) を求める
    for right in range(n):
        # 区間の長さが K を超える間、左端のポインタを進める
        while x[right] - x[left] > k:
            left += 1
        
        # 現在の区間内に含まれる木の数
        current_trees = right - left + 1
        
        # 最大値を更新
        if current_trees > max_trees:
            max_trees = current_trees
            
    # 結果を出力
    print(max_trees)

if __name__ == "__main__":
    main()

This editorial was generated by gemini-3-flash-preview.