Circuits

Interview

Time limit2sMemory limit512 MB

Summary
Given axis-aligned rectangles, choose two horizontal lines to maximize how many distinct rectangles they touch along a top or bottom side.
Level

Medium6 of 10

Topics
Sorting, Array, Greedy, Implementation
Solved
No attempts yet

Problem

A number of electronic circuits, such as CPUs, ROMs, and RAMs, are to be printed into a single chip made of multiple layers. Because of a design restriction, only two electrical wires that are horizontal segments can be placed. Your job is to find two horizontal wires that together connect as many circuits as possible so that the electric signals go through the circuits.

This problem can be stated formally as follows. There are n axis-aligned rectangles in the plane. Each rectangle represents a circuit to be printed into the chip. The rectangles may overlap each other. You are to find two horizontal lines such that the total number of rectangles intersected by the two lines is maximized. A rectangle is intersected by a horizontal line if the line contains the top side or the bottom side of the rectangle. If a rectangle is intersected by both lines, it is counted only once for the total number.

For example, consider the 5 rectangles shown in Figure A.1. Figure A.1(c) shows two horizontal lines (red dashed lines) that intersect all 5 rectangles, while the two horizontal lines (red dashed lines) in Figure A.1(b) intersect 4 rectangles.

Figure A.1: (a) 5 axis-aligned rectangles. (b) Two horizontal lines that intersect 4 rectangles. (c) Two horizontal lines that intersect 5 rectangles.

Given a set of axis-aligned rectangles, write a program to find two horizontal lines such that the total number of rectangles intersected by the two lines is maximized.

Input

Your program is to read from standard input. The first line contains a positive integer n, the number of axis-aligned rectangles in the plane, where 3 ≤ n ≤ 100,000. It is followed by n lines, each containing four integers ux, uy, vx, and vy (with ux < vx and uy > vy) giving the (x, y)-coordinates (ux, uy) of the top-left corner and the (x, y)-coordinates (vx, vy) of the bottom-right corner of an axis-aligned rectangle, where −10,000,000 ≤ ux, uy, vx, vy ≤ 10,000,000.

Output

Your program is to write to standard output. Print exactly one line. The line should contain the maximum total number of rectangles that can be intersected by two horizontal lines.

Examples2

  1. Example 1

    Input
    5
0 13 4 4
2 14 11 9
7 17 12 12
3 5 16 0
5 2 13 1
    Expected output
    5

  2. Example 2

    Input
    5
0 4 4 0
1 3 3 1
5 8 9 4
0 12 4 8
1 11 3 9
    Expected output
    4