`
zhang_xzhi_xjtu
  • 浏览: 538501 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

Intervals P1089 ACM Problem

阅读更多
Description

There is given the series of n closed intervals [ai; b i], where i=1,2,...,n. The sum of those intervals may berepresented as a sum of closed pairwise non−intersecting intervals. The task is to find such representation with the minimal number of intervals. The intervals of this representation should be written in the output file in acceding order. We say that the intervals [a; b] and [c; d] are in ascending order if, and only if a <= b < c <= d.
Task
Write a program which:
.reads from the std input the description of the series of intervals,
.computes pairwise non−intersecting intervals satisfying the conditions given above,
.writes the computed intervals in ascending order into std output
Input

In the first line of input there is one integer n, 3 <= n <= 50000. This is the number of intervals. In the (i+1)−st line, 1 <= i <= n, there is a description of the interval [ai; bi] in the form of two integers ai and bi separated by a single space, which are respectively the beginning and the end of the interval,1 <= ai <= bi <= 1000000.
Output

The output should contain descriptions of all computed pairwise non−intersecting intervals. In each line should be written a description of one interval. It should be composed of two integers, separated by a single space, the beginning and the end of the interval respectively. The intervals should be written into the output in ascending order.
Sample Input

5
5 6
1 4
10 10
6 9
8 10
Sample Output

1 4
5 10

package p1089;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);

		IntervalSet intervalSet = new IntervalSet();

		int count = in.nextInt();

		for (int i = 0; i < count; i++) {
			Interval tmpInterval = new Interval();
			tmpInterval.start = in.nextInt();
			tmpInterval.end = in.nextInt();
			intervalSet.addInterval(tmpInterval);
		}

		intervalSet.printInfo();
	}

	private static class Interval {
		int start;
		int end;

		public Interval() {
		}

		public boolean isOverlap(Interval interval) {
			return !(this.start > interval.end || interval.start > this.end);
		}

		public void merge(Interval interval) {
			this.start = Math.min(this.start, interval.start);
			this.end = Math.max(this.end, interval.end);
		}

		public void printInfo() {
			System.out.println(start + " " + end);
		}

	}

	private static class IntervalSet {
		List<Interval> list = new ArrayList<Interval>();

		boolean isOverlap(int position, Interval interval) {
			return list.get(position).isOverlap(interval);
		}

		/**
		 * return -1 if there is no overlap.
		 */
		int findOverlapStart(int start, int end, Interval interval) {
			if (start > end)
				return -1;
			if (start == end) {
				return isOverlap(start, interval) ? start : -1;
			}

			int middle = (start + end) / 2;

			Interval middleInterval = list.get(middle);
			if (middleInterval.isOverlap(interval)) {
				return findOverlapStart(start, middle, interval);
			} else if (interval.start < middleInterval.start) {
				return findOverlapStart(start, middle - 1, interval);
			} else {
				return findOverlapStart(middle + 1, end, interval);
			}
		}

		int findOverlapEnd(int start, int end, Interval interval) {
			if (start > end)
				return -1;
			if (start == end) {
				return isOverlap(start, interval) ? start : -1;
			}
			// if there are 2 element in the range, we should test it out.
			if (start + 1 == end) {
				if (isOverlap(end, interval))
					return end;
				if (isOverlap(start, interval))
					return start;
				return -1;
			}

			int middle = (start + end) / 2;

			Interval middleInterval = list.get(middle);
			if (middleInterval.isOverlap(interval)) {
				return findOverlapEnd(middle, end, interval);
			} else if (interval.start < middleInterval.start) {
				return findOverlapEnd(start, middle - 1, interval);
			} else {
				return findOverlapEnd(middle + 1, end, interval);
			}
		}

		int findInsertPosition(int start, int end, Interval interval) {
			if (start == end) {
				return start;
			}
			int middle = (start + end) / 2;
			Interval middleInterval = list.get(middle);

			if (middleInterval.start > interval.start) {
				return findInsertPosition(start, middle, interval);
			} else {
				return findInsertPosition(middle + 1, end, interval);
			}
		}

		/**
		 * find the position to insert.
		 */
		int findInsertPosition(Interval interval) {

			if (interval.start > list.get(list.size() - 1).start)
				return list.size();
			return findInsertPosition(0, list.size() - 1, interval);

		}

		/**
		 * return -1 if there is no overlap.
		 */
		int findOverlapStart(Interval interval) {
			return findOverlapStart(0, list.size() - 1, interval);
		}

		/**
		 * return -1 if there is no overlap.
		 */
		int findOverlapEnd(Interval interval) {
			return findOverlapEnd(0, list.size() - 1, interval);
		}

		void addInterval(Interval interval) {
			// 空list情况.
			int size = list.size();
			if (size == 0) {
				list.add(interval);
				return;
			}

			int overlapStart = findOverlapStart(interval);
			// There is no overlap.
			if (overlapStart == -1) {
				int insertPosition = findInsertPosition(interval);
				list.add(insertPosition, interval);
				return;
			}
			int overlapEnd = findOverlapEnd(interval);

			list.get(overlapStart).merge(interval);
			list.get(overlapStart).merge(list.get(overlapEnd));

			for (int i = overlapEnd; i > overlapStart; i--) {
				list.remove(i);
			}
		}

		void printInfo() {
			for (int i = 0; i < list.size(); i++) {
				list.get(i).printInfo();
			}
		}
	}
}


分享到:
评论

相关推荐

    Sifting Function Partition by Intervals for the Goldbach Problem

    金巴问题的筛函数按区间分割法,这个研究领域主要关注的是素数分布的问题。金巴猜想是数论中一个著名的未解决问题,它断言:任一大于2的偶数可以表示为两个素数之和。这个猜想虽然已经得到很多数值上的验证,但至今...

    Existence of Three Positive Solutions forWeighted p-Laplacian Boundary Value \Problemson Infinite Intervals

    Existence of Three Positive Solutions for Weighted p-Laplacian Boundary Value Problemson Infinite Intervals,Song Huijuan ,Yin Jingxue ,This paper is concerned with the existence of multiple ...

    浙江大学ACM题解/ZJU 题型分类

    1396 The Umbrella Problem: 2054 简单题 1058 Currency Exchange 简单题 1076 Gene Assembly 简单题 1092 Arbitrage 简单题 1093 Monkey and Banana 简单题 1094 Matrix Chain Multiplication 简单题 ...

    ACM POJ PKU 最全题目分类

    4. **1508 - Intervals**:区间问题。 5. **1333 - Galactic Import**:银河贸易问题。 6. **1304 - Tin Cutter**:剪切问题。 7. **1310 - Robot**:机器人移动问题。 8. **1311 - Network**:网络连接问题。 9. **...

    POJ1201-Intervals

    【标题】"POJ1201-Intervals" 是北京大学在线编程平台POJ上的一道题目,这道题目主要涉及计算机科学中的算法设计与分析,尤其是数据结构和时间复杂度优化方面的知识。 【描述】"北大POJ1201-Intervals 解题报告+AC...

    Dark.Intervals.Guitars.In.Space.KONTAKT-DECiBEL.rar

    Dark.Intervals.Guitars.In.Space.KONTAKT-DECiBE 解压密码:123 安装说明:https://blog.csdn.net/hongfu951/article/details/118517942 影视配乐吉他音源

    POJ1716-Integer Intervals【Difference Constraints】

    【标题】"POJ1716-Integer Intervals【Difference Constraints】" 是一个编程竞赛题目,来源于北京大学的在线评测系统POJ(Problem Online Judge)。这个题目主要涉及到差分约束系统(Difference Constraints)的...

    ACM国际大学生程序设计大赛学习资料:贪心算法精讲

    ### ACM国际大学生程序设计大赛学习资料:贪心算法精讲 #### 一、贪心算法简介 贪心算法是一种在每个阶段都采取最好或最优化的选择策略,希望以各阶段的局部最优达到全局最优的算法设计策略。这种算法通常简单易懂...

    ACM算法模板和pku代码

    本科参加ACM竞赛的过程中积累下来的一部分算法模板,和自己在PKU上面做的一部分题目。 模板目录结构: 目录: 动态规划 O(n^2)的最长上升子序列 nlogn最长上升子序列 高精度 计算几何 Graham扫描法 两线段交点 凸...

    acm贪心 gone fishing

    For each i = 1,...,n - 1, the number of 5-minute intervals it takes to travel from lake i to lake i + 1 is denoted ti (0 ). For example, t3 = 4 means that it takes 20 minutes to travel from lake 3 to...

    PyPI 官网下载 | python-intervals-1.5.1.tar.gz

    **Python-intervals 库详解** `python-intervals` 是一个基于 Python 的库,主要用于处理和操作数值区间。这个库提供了一种高效且直观的方式来创建、组合和查询数值范围,广泛应用于数据分析、数学计算以及需要处理...

    东京大学ACM模版,包含代码示例

    根据给定的信息,我们可以从东京大学的ACM模板中提炼出一些重要的算法和技术知识点,主要集中在数据结构领域。以下是对这些知识点的详细说明: ### 一、基础代码框架 在提供的部分代码中,可以看到一个非常典型的...

    Python库 | python_intervals-1.0.3-py3-none-any.whl

    《Python库:深入理解python_intervals-1.0.3-py3-none-any.whl》 在Python编程领域,丰富的库支持是其强大的原因之一。今天我们要探讨的是`python_intervals`库,一个专门处理区间操作的库,版本号为1.0.3。这个库...

    Python库 | python-intervals-1.7.0.tar.gz

    在本例中,我们关注的是名为"python-intervals-1.7.0.tar.gz"的压缩包,这显然是一个针对Python的库,主要用于处理区间或时间段相关的操作。 "python-intervals"库是一个强大的Python模块,它允许用户方便地创建、...

    java-leetcode题解之Merge Intervals.java

    java java_leetcode题解之Merge Intervals.java

    ICCs_with_confidence_intervals.zip_Confidence_ICCS_confidence in

    Calculate any of 6 different ICCs with confidence intervals

    开源项目-Figure1-go-intervals.zip

    开源项目-Figure1-go-intervals.zip,Interval Sets library to manage integer intervals (my first open sourced library)

    PyPI 官网下载 | mbf_nested_intervals-0.2.0.tar.gz

    "mbf_nested_intervals-0.2.0.tar.gz"是一个从PyPI官网下载的Python库,其主要功能可能与处理嵌套区间有关。 首先,我们来详细解释一下这个库的名称。"mbf"可能是模块或项目作者的名字或缩写,"nested_intervals"则...

    acm ZJU分类

    ### ACM ZJU 分类详解 #### 一、概述 在计算机科学竞赛领域,特别是算法设计与编程比赛中,ZJU(浙江大学)以其丰富的题目库和高质量的算法挑战而闻名。本篇旨在对ZJU题库中的部分题目进行详细的分类解析,并针对...

    ZJU_ACM_All_Anwer 搞编程的都知道的浙江大学A 题库.本书 集了所有经 Z 题解集,集合并附 Mathimaticsumerical algorithms 数值算法

    1396 The Umbrella Problem: 2054 简单题 1058 Currency Exchange 简单题 1076 Gene Assembly 简单题 1092 Arbitrage 简单题 1093 Monkey and Banana 简单题 1094 Matrix Chain Multiplication 简单题 ...

Global site tag (gtag.js) - Google Analytics